HDU - 5521 Meeting——增点建边+最短路

HDU - 5521 Meeting——增点建边+最短路

#include #include #include #include #include #include using namespace std;typedef pair P;const long long INF = 1e18;const int maxn = 2 * 1e6;bool vis[maxn];int n, m;long long dis1[maxn], dis2[maxn];vector

G[maxn];void dijkstra(int s, long long *dis) { for (int i = 0; i <= n + m; i++) vis[i] = false, dis[i] = INF; dis[s] = 0; priority_queue, greater

> q; q.push(make_pair(0, s)); while (!q.empty()) { int u = q.top().second; q.pop(); if (vis[u]) continue; vis[u] = true; for (unsigned int i = 0; i < G[u].size(); i++) { long long v = G[u][i].first, cost = G[u][i].second; if (dis[v] > dis[u] + cost) { dis[v] = dis[u] + cost; q.push(make_pair(dis[v], v)); } } }}int main() { int T; scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d %d", &n, &m); for (int i = 0; i <= n + m; i++) G[i].clear(); for (int i = 1; i <= m; i++) { int t, s, x; scanf("%d %d", &t, &s); for (int j = 1; j <= s; j++) { scanf("%d", &x); G[x].push_back(make_pair(n + i, t)); G[n + i].push_back(make_pair(x, t)); } } dijkstra(1, dis1); dijkstra(n, dis2); long long ans = INF; for (int i = 1; i <= n; i++) { long long temp = max(dis1[i], dis2[i]); ans = min(ans, temp); } printf("Case #%d: ", kase); if (ans == INF) printf("Evil John\n"); else { printf("%lld\n", ans / 2); int flag = 0; for (int i = 1; i <= n; i++) { long long temp = max(dis1[i], dis2[i]); if (temp == ans) { if (flag++) printf(" "); printf("%d", i); } } printf("\n"); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。