题目大意:有n个点,每个点连出一些有向边,每个点的第一条边权值为0,其他边权值为1,求某两点的最短路径。
解题思路:最短路径,由于n才到100,用Floyd乱搞即可。注意可能有点没有连出边(开始时我是k和第一条边连的点一起读入,就挂了TAT)!!时间复杂度$O(n^3)$。
C++ Code:
#include<cstdio> #include<cstring> using namespace std; int n,s,t; int dis[105][105]; int main(){ scanf("%d%d%d",&n,&s,&t); memset(dis,0x3f,sizeof(dis)); for(int i=1;i<=n;++i){ int k,f; scanf("%d",&k); if(k==0)continue; scanf("%d",&f); dis[i][f]=0; while(--k){ scanf("%d",&f); dis[i][f]=1; } } for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) if(k!=i) for(int j=1;j<=n;++j) if(j!=k&&j!=i){ if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j]; } if(dis[s][t]!=0x3f3f3f3f) printf("%d ",dis[s][t]);else puts("-1"); return 0; }