HDU 5521 Meeting （最短路，dijstra）

题意：有N个点，两个人，其中一个人住在点1，另一个人住在点n，有M个点集，集合内的数表示任意两点的距离为dis ，现在问，如果两个人要见面，

需要最短距离是多少，有哪几个点能被当成见面点。

析：分别对1和n进行最短路操作，这个题最让人别扭的就是边太多，如果你直接全部都存下来，那么一定会MLE，所以一定要优化边。所以我们要把每一行的边都记下来，

而不是两两都记下，然后把每一行的编号记下来，最后要查询时，就行编号去定位到哪一行，这样就不会超内存。这里会了，其他的就很简单了。

代码如下：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <stack>
using namespace std;

typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const LL LNF = 100000000000000000;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const char *mark = "+-*";
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
int n, m;
inline bool is_in(int r, int c){
    return r >= 0 && r < n && c >= 0 && c < m;
}
inline LL Max(LL a, LL b){  return a < b ? b : a; }
inline LL Min(LL a, LL b){  return a > b ? b : a; }
vector<int> G[maxn];
vector<int> b[maxn];
LL d1[maxn];
LL d2[maxn];
int t[maxn];
bool vis[maxn];

void dijstra(int s, LL* d){
    priority_queue<P, vector<P>, greater<P> > pq;
    pq.push(P(0, s));
    memset(vis, false, sizeof vis);
    fill(d, d+n+1, LNF);
    d[s] = 0;

    while(!pq.empty()){
        P p = pq.top();  pq.pop();
        int u = p.second;
        if(d[u] < p.first) continue;
        for(int i = 0; i < b[u].size(); ++i){//从编号找出在哪行
            int v = b[u][i];
            if(vis[v])  continue;
            vis[v] = true;
            for(int j = 0; j < G[v].size(); ++j){
                int uv = G[v][j], w = t[v];
                if(d[uv] > d[u] + w){
                    d[uv] = d[u] + w;
                    pq.push(P(d[uv], uv));
                }
            }
        }
    }
}

int main(){
    int T;  cin >> T;
    for(int kase = 1; kase <= T; ++kase){
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; ++i)  G[i].clear(), b[i].clear();
        for(int i = 1; i <= m; ++i){
            int k;
            scanf("%d %d", &t[i], &k);
            for(int j = 0; j < k; ++j){
                int v;
                scanf("%d", &v);
                G[i].push_back(v);//存边
                b[v].push_back(i);//记下行号
            }
        }

        dijstra(1, d1);
        dijstra(n, d2);
        printf("Case #%d: ", kase);
        LL ans = LNF;
        for(int i = 1; i <= n; ++i)
            ans = Min(ans, Max(d1[i], d2[i]));
        if(ans == LNF)  puts("Evil John");
        else{
            printf("%I64d
", ans);
            int cnt = 0;
            for(int i = 1; i <= n; ++i)
                if(ans == Max(d1[i], d2[i])){
                    if(cnt)  putchar(' ');
                    printf("%d", i);
                    ++cnt;
                }
            printf("
");
        }
    }
    return 0;
}