hdu 5521 图论最短路

我会带着你远行 2022-08-10 03:54 6阅读 0赞

# Meeting #

**Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)  
Total Submission(s): 762    Accepted Submission(s): 239**

Problem Description

Bessie and her friend Elsie decide to have a meeting. However, after Farmer John decorated his  
fences they were separated into different blocks. John's farm are divided into  *n* blocks labelled from  1 to  *n*.  
Bessie lives in the first block while Elsie lives in the  *n*\-th one. They have a map of the farm  
which shows that it takes they  *t**i* minutes to travel from a block in  *E**i* to another block  
in  *E**i* where  *E**i* (1≤*i*≤*m*) is a set of blocks. They want to know how soon they can meet each other  
and which block should be chosen to have the meeting.

Input

The first line contains an integer  *T* (1≤*T*≤6), the number of test cases. Then  *T* test cases  
follow.  
  
The first line of input contains  *n* and  *m*.  2≤*n*≤105. The following  *m* lines describe the sets  *E**i* (1≤*i*≤*m*). Each line will contain two integers  *t**i*(1≤*t**i*≤109) and  *S**i* (*S**i*>0) firstly. Then  *S**i* integer follows which are the labels of blocks in  *E**i*. It is guaranteed that  ∑*m**i*=1*S**i*≤106.

Output

For each test case, if they cannot have the meeting, then output "Evil John" (without quotes) in one line.  
  
Otherwise, output two lines. The first line contains an integer, the time it takes for they to meet.  
The second line contains the numbers of blocks where they meet. If there are multiple  
optional blocks, output all of them in ascending order.

Sample Input

2
    5 4
    1 3 1 2 3
    2 2 3 4
    10 2 1 5
    3 3 3 4 5
    3 1
    1 2 1 2

Sample Output

Case #1: 3
    3 4
    Case #2: Evil John
    
       
        Hint In the first case, it will take Bessie 1 minute travelling to the 3rd block, and it will take Elsie 3 minutes travelling to the 3rd block. It will take Bessie 3 minutes travelling to the 4th block, and it will take Elsie 3 minutes travelling to the 4th block. In the second case, it is impossible for them to meet.

Source

[2015ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学） ][2015ACM_ICPC_-_]

题意：有n个点，分成了m块，每个块内点到点之间的距离都是dis，两个人分别在点1和点n；求最短距离的条件下两人能够在哪些点见面；

分析：重现赛的时候并不会。赛后搜了搜题解，像我这种弱弱也只能跑去看题解了D:

法1：vector s记录第i个块内有哪些点，a表示第i个点存在于哪些块中。然后跑两次dijkstra，更新最短路的过程中记录哪些块已经被更新，以后就不用更新了，同时记录哪些点已经被更新，以后也不用更新了。具体原理并不是很清楚，只是感觉是对的。。。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 100000000000000000
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,ll> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=3000100;
    
    int ans[N];
    vector<int> s[N],a[N];
    bool vis[N],use[N];
    int t[N];
    priority_queue<pii,vector<pii>,greater<pii> > q,qq;
    
    void dijkstra(ll xx,ll *dis,int n)
    {
        for(int i=0;i<=n;i++) dis[i]=inf;
        dis[xx]=0;
        pii now;
        q.push(pii(dis[xx],xx));
        mem(vis,0);
        mem(use,0);
        while(!q.empty())
        {
            now=q.top();
            q.pop();
            int x = now.second;
            if(vis[x]) continue;
            vis[x]=1;
            for(int i=0;i<a[x].size();i++)
            {
                int tm=a[x][i];
                if(use[tm]) continue;
                use[tm]=1;
                for(int j=0;j<s[tm].size();j++)
                {
                    int tmp=s[tm][j];
                    if(tmp == x) continue;
                    if(dis[x]+t[tm] < dis[tmp])
                    {
                        dis[tmp] = dis[x]+t[tm];
                        q.push(pii(dis[tmp],tmp));
                    }
                }
            }
        }
    }
    
    ll dis[N];
    ll dis2[N];
    
    int main()
    {
        int T=in();
        int ii=1,tt,nn;
        while(T--)
        {
            int n=in(),m=in();
            for(int i=0;i<=max(n,m);i++)
            {
                s[i].clear();
                a[i].clear();
            }
    
            for(int i=1;i<=m;i++)
            {
                t[i]=in(),nn=in();
                while(nn--)
                {
                    int x=in();
                    s[i].push_back(x);
                    a[x].push_back(i);
                }
            }
            dijkstra(1,dis,n);
            dijkstra(n,dis2,n);
            ll mn=inf;
            for(int i=1;i<=n;i++)
            {
                mn=min(mn,max(dis[i],dis2[i]));
            }
            if(mn==inf)
            {
                printf("Case #%d: Evil John\n",ii++);
                continue;
            }
            int cnt=0;
            for(int i=1;i<=n;i++)
            {
                if(mn == max(dis[i],dis2[i]))
                {
                    ans[cnt++]=i;
                }
            }
            printf("Case #%d: %I64d\n",ii++,mn);
            for(int i=0;i<cnt;i++)
            {
                printf("%d%c",ans[i],i==cnt-1? '\n' : ' ');
            }
        }
        return 0;
    }

法2：拆点。以前做过一道拆点的题，还是有一点感觉的。。

入点是n+2\*i-1， 出点是n+2\*i，入点到出点连接一条长度为dis的边，

块内所有的点到入点连边，距离为0，

出点连接块内所有的点 ， 距离为0；

这样总数就是3\*n；

然后跑两遍dijkstra就行了。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 100000000000000000
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,ll> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=3000100;
    struct st
    {
        int to,cost;
    };
    
    int ans[100010];
    vector<st> s[N];
    bool vis[N];
    int d;
    priority_queue<pii,vector<pii>,greater<pii> > q;
    
    void dijkstra(ll xx,ll *dis,int n)
    {
        for(int i=0;i<=n;i++) dis[i]=inf;
        dis[xx]=0;
        pii now;
        q.push(pii(dis[xx],xx));
        mem(vis,0);
        while(!q.empty())
        {
            now=q.top();
            q.pop();
            int x = now.second;
            if(vis[x]) continue;
            vis[x]=1;
            for(int i=0;i<s[x].size();i++)
            {
                st tmp=s[x][i];
                if(dis[tmp.to] > dis[x]+tmp.cost)
                {
                    dis[tmp.to] = dis[x]+tmp.cost;
                    q.push(pii(dis[tmp.to],tmp.to));
                }
            }
        }
    }
    
    ll dis[N];
    ll dis2[N];
    
    int main()
    {
        int T=in();
        int ii=1,tt,nn;
        while(T--)
        {
            int n=in(),m=in();
            for(int i=0;i<=n+2*m;i++)
            {
                s[i].clear();
            }
            for(int i=1;i<=m;i++)
            {
                d=in(),nn=in();
                s[n+2*i-1].push_back(st{n+2*i,d}); //拆点~ 入点到出点连接一条边 距离为输入的d
                while(nn--)
                {
                    int x=in();
                    s[x].push_back(st{n+2*i-1,0}); //里面的每一个点连接到入点  距离为0
                    s[n+2*i].push_back(st{x,0});    //出点连接到每一个点  距离为0
                }
            }
            dijkstra(1,dis,n+2*m);
            dijkstra(n,dis2,n+2*m);
            ll mn=inf;
            for(int i=1;i<=n;i++)
            {
                mn=min(mn,max(dis[i],dis2[i]));
            }
            if(mn==inf)
            {
                printf("Case #%d: Evil John\n",ii++);
                continue;
            }
    
            int cnt=0;
            for(int i=1;i<=n;i++)
            {
                if(mn == max(dis[i],dis2[i]))
                {
                    ans[cnt++]=i;
                }
            }
            printf("Case #%d: %I64d\n",ii++,mn);
            for(int i=0;i<cnt;i++)
            {
                printf("%d%c",ans[i],i==cnt-1? '\n' : ' ');
            }
        }
        return 0;
    }

[2015ACM_ICPC_-_]: http://acm.hdu.edu.cn/search.php?field=problem&key=2015ACM%2FICPC%D1%C7%D6%DE%C7%F8%C9%F2%D1%F4%D5%BE-%D6%D8%CF%D6%C8%FC%A3%A8%B8%D0%D0%BB%B6%AB%B1%B1%B4%F3%D1%A7%A3%A9&source=1&searchmode=source