题意：
现在给出一个图,其中分成点分成一个集合一个集合的,每一集合中的点互相之间的距离都是相同的,也给出来了;现在要求两个人分别从1和n出发,问最短多长时间才能遇到,且给出这些可能的相遇点;
思路：
建m个源点，这m个集合每个集合建一个源点，然后集合里的点与本集合的源点连一条指向源点的权值为w的边，再连一条反向边权值为0，然后跑最短路，输出可能的相遇点。
#include<bits/stdc++.h> #define ll long long #define MP make_pair #define P pair<long long, int> using namespace std; const int N = 4e6 + 10; int T, n, m, h[N], cnt, vis[N]; ll dis[2][N], ans; struct node { int v, w, nt; } no[N]; void add(int u, int v, int w) { no[cnt] = node{v, w, h[u]}; h[u] = cnt++; } void dijkstra(int s, int sta) { memset(dis[sta], 0x3f, sizeof dis[sta]); memset(vis, 0, sizeof vis); priority_queue<P> q; dis[sta][s] = 0; q.push(MP(0, s)); while(!q.empty()) { int u = q.top().second; q.pop(); if(vis[u]) continue; vis[u] = 1; for(int i = h[u]; ~i; i = no[i].nt) { int v = no[i].v; if(dis[sta][v] > dis[sta][u] + no[i].w) { dis[sta][v] = dis[sta][u] + no[i].w; if(!vis[v]) q.push(MP(-dis[sta][v], v)); } } } } int main() { scanf("%d", &T); int kk = 1; while(T--) { memset(h, -1, sizeof h); ans = 1e18, cnt = 0; scanf("%d%d", &n, &m); for(int num, k, w, i = 1; i <= m; i++) { scanf("%d%d", &w, &num); while(num--) { scanf("%d", &k); add(n + i, k, w); add(k, n + i, 0); } } dijkstra(1, 0); dijkstra(n, 1); int num; for (int i = 1; i <= n; ++i) if (ans >= max(dis[0][i], dis[1][i])) { ans = max(dis[0][i], dis[1][i]); num = i; } if (ans == 1e18) printf("Case #%d: Evil John\n", kk++); else { printf("Case #%d: %lld\n", kk++, ans); for (int i = 1; i <= n; ++i) if (ans == max(dis[0][i], dis[1][i])) { printf("%d", i); if (i != num) printf(" "); } printf("\n"); } } return 0; }
