HDU 5521 Meeting（巧妙地构图的最短路）

梦里梦外; 2022-07-16 04:21 170阅读 0赞

题目链接：  
[http://acm.hdu.edu.cn/showproblem.php?pid=5521][http_acm.hdu.edu.cn_showproblem.php_pid_5521]  
题目大意：（补题解中先把思路码上）

解题思路：n个点，两两距离为x，按正常的思路想要建n^2条边，实际上建2\*n+1条边就可以了，建立一个源点，建n条边使n个点到源点的距离为0，再建立一个汇点，源点到汇点的距离为x，再从汇点到n个点建立一条距离为0的边，即可等价为刚才的图。

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <set>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    
    #define MAX_V 1300005
    
    LL inff=1e17;
    
    struct edge
    {
        int to;
        LL cost;
    };
    
    int V,n,m;
    typedef pair<LL,int> P;
    vector<edge> vec[MAX_V];
    
    LL d[MAX_V];
    LL ans[MAX_V];
    void dijkstra(int s)
    {
        V=n+m*2+10;
        priority_queue<P, vector<P>,greater<P> >que;
        fill(d,d+V,inff);
        d[s]=0;
        que.push(P(0,s));
        while(!que.empty())
        {
            P p=que.top();
            que.pop();
            int v=p.second;
            if(d[v]<p.first) continue;
            for(int i=0;i<vec[v].size();i++)
            {
                edge e=vec[v][i];
                if(d[e.to]>d[v]+e.cost)
                {
                    d[e.to]=d[v]+e.cost;
                    que.push(P(d[e.to],e.to));
                }
    
            }
    
        }
    
    
    }
    
    int main()
    {
        int T,cas=1;;
        RI(T);
        while(T--)
        {
            RII(n,m);
            for(int i=1; i<=m; i++)
            {
                LL t,s;
                scanf("%I64d %I64d",&t,&s);
                for(int j=1; j<=s; j++)
                {
                    int x;
                    RI(x);
                    edge e;
                    e.to=n+i*2-1;
                    e.cost=0;
                    vec[x].push_back(e);
                    e.to=n+i*2;
                    e.cost=t;
                    vec[n+i*2-1].push_back(e);
                    e.to=x;
                    e.cost=0;
                    vec[n+i*2].push_back(e);
                }
            }
            dijkstra(1);
            for(int i=1;i<=n;i++)
            ans[i]=d[i];
            dijkstra(n);
            LL q=inff;
            for(int i=1;i<=n;i++)
            {
                ans[i]=max(ans[i],d[i]);
                if(q>ans[i])  q=ans[i];
            }
            if(q==inff)
            {
                printf("Case #%d: Evil John\n",cas++);
            }
            else
            {
                printf("Case #%d: %I64d\n",cas++,q);
                int i=1;
                for(;i<=n;i++)
                {
                    if(q==ans[i])
                    {
                        printf("%d",i);
                        i++;
                        break;
                    }
                }
                for(;i<=n;i++)
                {
                    if(q==ans[i])
                        printf(" %d",i);
                }
                printf("\n");
            }
            for(int i=0;i<=V;i++)
            vec[i].clear();
    
    
        }
    
    
    
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5521]: http://acm.hdu.edu.cn/showproblem.php?pid=5521