题目描述：
给定一张图，问从1和n相遇的最短时间。
这道题的输入比较特殊，不能直接存，所以怎么输入，怎么存取，只要可以访问到一个节点的相邻节点就可以，由于spfa算法的时间复杂度为m*n，而Dijkstra算法的时间复杂度为m*log(n),
其实Dijkstra就是用优先队列替换掉了spfa中的普通队列，每次都是用权值最小的点去更新别人，可以这么理解，用用权值最小的点a去更新其他节点，在更新节点中必然会有一个节点已经是
最短路，假设是b，因为源点到其他节点的距离+其他节点到b节点的距离 > dist[a] + edge[a][b], 因为 源点到其他节点的距离 > dist[a] + edge[a][b]；最多有10^6个点，那么可能就会有 10^12条边 ，时间复杂度为 10^12 * log(10^5) = 15*10^12;所以主要取决于有多少条边，分析一下如果一个节点已经更新了它所在集合中的其他点，那么这个集合中所有点之间的边就不会在更新了，假设a,b,c,d,e在一个集合里，集合之间的路径为edge，假设a是更新点，说明b，c，d，e的最短路大于a的最短路， 说明b，c，d的最短路一定是由a得到，而不是 b，c，d，Dis[a]+edge < Dist[k] +edge，k属于b,c,d。所以集合只会被访问一次。
//有可能一个人在家等他 #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> #include <algorithm> #include <math.h> #define maxn 1100000 #define LL long long using namespace std; int t; int n,m; vector < int > G[maxn]; int tt[maxn],ss[maxn]; vector < int > Set[maxn]; LL Dist[3][maxn]; int vis[maxn]; int VISIT[maxn]; LL answer[maxn]; LL ans[maxn]; struct node { int u,dist; friend bool operator < (node a,node b) { return a.dist>b.dist; } }; void init() { memset(vis,0,sizeof(vis)); memset(VISIT,0,sizeof(VISIT)); } void Dijkstra(int start) { int kind; if(start==1) kind=1; else kind=2; priority_queue < node > que; node s; s.u=start; s.dist=0; Dist[kind][start]=0; que.push(s); while(!que.empty()) { s=que.top(); que.pop(); if(vis[s.u]==1) continue; vis[s.u]=1; int from=s.u; for(int i=0;i<Set[from].size();i++) //找到所在集合 { int j=Set[from][i]; //j代表哪个集合 if(VISIT[j]==1) continue; VISIT[j]=1; int edge= tt[j]; //edge代表长度 for(int k=0;k<G[j].size();k++) //遍历相邻节点 { node Next; int to=G[j][k]; if(Dist[kind][to]>Dist[kind][from]+edge || Dist[kind][to]==-1 ) { Dist[kind][to]=Dist[kind][from] + edge; Next.dist=Dist[kind][to]; Next.u=to; que.push(Next); } } } } } void solve() { init(); Dijkstra(1); init(); Dijkstra(n); for(int i=1;i<=n;i++) { // cout<<Dist[1][i]<<" "<<Dist[2][i]<<endl; if(Dist[1][i]==-1 || Dist[2][i]==-1) answer[i]=-1; else answer[i]=max(Dist[1][i],Dist[2][i]); } LL MIN=-1; for(int i=1;i<=n;i++) { if(MIN > answer[i] || (MIN==-1) ) MIN=answer[i]; } if(MIN==-1) printf("Evil John\n"); else { printf("%I64d\n",MIN); int flag=0; for(int i=1;i<=n;i++) { if(MIN==answer[i]) { if(flag==1) printf(" "); printf("%d",i); flag=1; } } printf("\n"); } } void input() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&tt[i],&ss[i]); for(int j=1;j<=ss[i];j++) { int input; scanf("%d",&input); G[i].push_back(input); Set[input].push_back(i); } } } void Init() { for(int i=0;i<maxn;i++) { G[i].clear(); Set[i].clear(); } memset(Dist,-1,sizeof(Dist)); } int main() { //freopen("test.txt","r",stdin); scanf("%d",&t); int Case=0; // printf("%d\n",inf); // cout<<inf<<endl; while(t--) { Init(); input(); printf("Case #%d: ",++Case); solve(); } return 0; }