0144-Packet Transportation

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0144
2点間の最短距離を求める問題。
2点の間には重みがないので、重みを1としてワーシャルフロイト法で2点間の最短距離を求める。
TTLよりも最短距離が大きかった場合は到達できないのでNAを出力するようにする。

実装(C++/インクルード省略)

#define INF 999999;
#define MAX_V 105
int V;
int d[MAX_V][MAX_V];
void warshall_floyd(){
	for(int k=0;k<V;k++){
		for(int i=0;i<V;i++){
			for(int j=0;j<V;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
}

int main(){
	int i,j;
	int m;
	int r,k,t;
	scanf("%d",&V);
	memset(d,0x10,sizeof(d));
	for(i=0;i<V;i++){
		scanf("%d%d",&r,&k);r-=1;
		d[r][r]=0;
		for(j=0;j<k;j++){
			scanf("%d",&t);
			d[r][t-1]=1;
		}
	}
	warshall_floyd();
	scanf("%d",&m);
	for(i=0;i<m;i++){
		scanf("%d %d %d",&r,&k,&t);
		j=d[r-1][k-1]+1;
		if(t<j) puts("NA");
		else printf("%d\n",j);
		fflush(stdout);
	}

	return 0;
}