【HDU5521】Meeting 最短路 + 优化建图

传送⻔

题意

有个图，有n个结点，有m个区域，相同的点可以在不同的区域中，同一区域内的点之间的距离都是一样的。有两个人分别在结点1和结点n，让两个人选择一个地方相聚，到达这个地方所用的时间最少。输出最少的时间，以及所有最短时间的点。

分析

最短路问题，怎么去建图呢
显然，一个集合里面两两建边是一件不太现实的事，考虑每一个集合建了一个虚点，那么集合之中的移动可以看成 点 - 虚点 - 点的移动

代码

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
#define _CRT_SECURE_NO_WARNINGS
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, int> PII;
typedef vector<int> VI;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10,M = N * 2;
const ll mod = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a) {
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}
int gcd(int a, int b) {return (b > 0) ? gcd(b, a % b) : a;}
int h[N],ne[M],e[M],idx;
ll w[M],d[N],d1[N],d2[N];
bool st[N];
int n,m;

void add(int x,int y,int z){
    ne[idx] = h[x],e[idx] = y,w[idx] = z,h[x] = idx++;
}

void dij(int s){
    for(int i = 0;i <= n + m + 1;i++) d[i] = INF,st[i] = false;
    d[s] = 0;
    priority_queue<PII,vector<PII>,greater<PII> > Q;
    Q.push(PII(0,s));
    while(Q.size()){
        PII p = Q.top();
        Q.pop();
        int t = p.second;
        if(st[t]) continue;
        st[t] = true;
        for(int i = h[t];i != -1;i = ne[i]){
            int j = e[i];
            if(d[j] > d[t] + w[i]){
                d[j] = d[t] + w[i];
                Q.push(PII(d[j],j));
            }
        }
    }
}


int main() {
    int T;
    read(T);
    for(int ppppp = 1;ppppp <= T;ppppp++){
        printf("Case #%d: ",ppppp);
        scanf("%d%d",&n,&m);
        for(int i = 0;i <= n + m + 1;i++) h[i] = -1;
        idx = 0;
        int s = n + 1;
        for(int i = 1;i <= m;i++){
            int num,t;
            scanf("%d%d",&t,&num);
            while(num--){
                int x;
                scanf("%d",&x);
                add(x,s,t);
                add(s,x,0);
            }
            s++;
        }
        dij(1);
        if(d[n] == INF) {
            puts("Evil John");
            continue;
        }
        for(int i = 1;i <= n;i++) d1[i] = d[i];
        dij(n);
        for(int i = 1;i <= n;i++) d2[i] = d[i];
        ll mi = INF;
        for(int i = 1;i <= n;i++) mi = min(mi,max(d1[i],d2[i]));
        dl(mi);
        VI nums;
        for(int i = 1;i <= n;i++) if(max(d1[i],d2[i]) == mi) nums.pb(i);
        printf("%d",nums[0]);
        for(int i = 1;i < nums.size();i++) printf(" %d",nums[i]);
        puts("");
    }
    return 0;
}