[HDOJ5521]Meeting（最短路）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5521

给n个点，m个块。块内点到点之间话费的时间ti。两个人分别从点1和点n出发，问两人是否可以相遇，并求出相遇最短时间和路径，路径按照字典序输出。

这题的难点在于处理块内的点到块外点的关系。我们可以添加一个“集合点”，此点到集合内各点距离为w，点到此集合的距离为0建图。

从1和n分别做一次最短路，找到每一个距离最长的点（即为相遇点），记下长度再枚举两个结果，看一共多少个相遇点

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <iomanip>
  4 #include <cstring>
  5 #include <climits>
  6 #include <complex>
  7 #include <fstream>
  8 #include <cassert>
  9 #include <cstdio>
 10 #include <bitset>
 11 #include <vector>
 12 #include <deque>
 13 #include <queue>
 14 #include <stack>
 15 #include <ctime>
 16 #include <set>
 17 #include <map>
 18 #include <cmath>
 19 
 20 using namespace std;
 21 
 22 typedef long long ll;
 23 typedef pair<int, int> pii;
 24 typedef struct E {
 25     int w;
 26     int v;
 27     E() {}
 28     E(int vv, int ww) : v(vv), w(ww) {}
 29 }E;
 30 
 31 const int inf = 0x7f7f7f7f;
 32 const int maxn = 200010;
 33 
 34 priority_queue<pii, vector<pii>, greater<pii> > pq;
 35 vector<E> e[maxn];
 36 vector<int> path;
 37 ll d[3][maxn];
 38 int n, m, u, v, w, k;
 39 
 40 template<int cho>
 41 void dijkstra(int s) {
 42     memset(d[cho], inf, sizeof(d[cho]));
 43     while(!pq.empty()) pq.pop();
 44     d[cho][s] = 0;
 45     pq.push(pii(0, s));
 46     while(!pq.empty()) {
 47         pii cur = pq.top(); pq.pop();
 48         w = cur.first;
 49         v = cur.second;
 50         if(d[cho][v] < w) continue;
 51         for(int i = 0; i < e[v].size(); i++) {
 52             if(d[cho][e[v][i].v] > d[cho][v] + e[v][i].w) {
 53                 d[cho][e[v][i].v] = d[cho][v] + e[v][i].w;
 54                 pq.push(pii(d[cho][e[v][i].v], e[v][i].v));
 55             }
 56         }
 57     }
 58 }
 59 
 60 inline bool scan_d(int &num) {
 61     char in;bool IsN=false;
 62     in=getchar();
 63     if(in==EOF) return false;
 64     while(in!='-'&&(in<'0'||in>'9')) in=getchar();
 65     if(in=='-'){ IsN=true;num=0;}
 66     else num=in-'0';
 67     while(in=getchar(),in>='0'&&in<='9'){
 68             num*=10,num+=in-'0';
 69     }
 70     if(IsN) num=-num;
 71     return true;
 72 }
 73 
 74 int main() {
 75     // freopen("in", "r", stdin);
 76     int T, _ = 1;
 77     scan_d(T);
 78     while(T--) {
 79         for(int i = 0; i < maxn; i++) e[i].clear();
 80         path.clear();
 81         scan_d(n); scan_d(m);
 82         for(int i = 1; i <= m; i++) {
 83             scan_d(w); scan_d(k);
 84             while(k--) {
 85                 scanf("%d", &v);
 86                 e[n+i].push_back(E(v, w));
 87                 e[v].push_back(E(n+i, 0));
 88             }
 89         }
 90         dijkstra<0>(1); dijkstra<1>(n);
 91         ll cur = inf;
 92         for(int i = 1; i <= n; i++) {
 93             cur = min(cur, max(d[0][i], d[1][i]));
 94         }
 95         for(int i = 1; i <= n; i++) {
 96             if(cur == max(d[0][i], d[1][i])) {
 97                 path.push_back(i);
 98             }
 99         }
100         printf("Case #%d: ", _++);
101         if(cur == inf) {
102             printf("Evil John
");
103             continue;
104         }
105         printf("%I64d
", cur);
106         for(int i = 0; i < path.size(); i++) {
107             printf("%d", path[i]);
108             if(i == path.size() - 1) printf("
");
109             else printf(" ");
110         }
111     }
112     return 0;
113 }