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; }