欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU5521(最短路+建边)

程序员文章站 2022-05-22 14:34:56
...

图论太菜了啊= =。
题解:每个集合外多加一个点,使得集合中的点和这集合外的点连起来,权值为cost,反过来建一条权值为0的边,然后从1跑spfa,从n跑spfa,那最短路就是max(dist1[i],dist2[i])中的最小值。枚举一下就可以

其实挺水的

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <vector>
#define mod  1000000007
#define INF  0x3f3f3f3f
#define fuck() (cout << "----------------------------------------" << endl)
using namespace std;
const int maxn = 2000000 + 5;
int dist1[maxn];
int dist2[maxn];
int queuenum[maxn];
bool vis[maxn];
int n,m;
struct Edge
{
    int to;
    int cost;
    Edge(){}
    Edge(int To, int Cost)
    {
        to = To;
        cost = Cost;
    }
};
vector <Edge> edge[maxn];
void init()
{
    for(int i=0; i<maxn; i++)
        edge[i].clear();
    memset(dist1,INF,sizeof(dist1));
    memset(dist2,INF,sizeof(dist2));
}
void addedge(int from, int to, int cost)
{
    edge[from].push_back(Edge(to,cost));
}
void spfa1(int source)
{
    memset(vis,false,sizeof(vis));
    memset(queuenum,0,sizeof(queuenum));
    dist1[source] = 0;
    queue < int > q;
    q.push(source);
    vis[source] = true;
    queuenum[source] = 1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i=0; i<edge[u].size(); i++)
        {
            Edge eg = edge[u][i];
            int to = eg.to;
            int cost = eg.cost;
            if(dist1[u] + cost < dist1[to])
            {
                dist1[to] = dist1[u] + cost;
                if(!vis[to])
                {
                    q.push(to);
                    queuenum[to]++;
                    if(queuenum[to] >= n+m)
                        return;
                    vis[to] = true;
                }
            }
        }
    }
    return;
}
void spfa2(int source)
{
    memset(vis,false,sizeof(vis));
    memset(queuenum,0,sizeof(queuenum));
    dist2[source] = 0;
    queue < int > q;
    q.push(source);
    vis[source] = true;
    queuenum[source] = 1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i=0; i<edge[u].size(); i++)
        {
            Edge eg = edge[u][i];
            int to = eg.to;
            int cost = eg.cost;
            if(dist2[u] + cost < dist2[to])
            {
                dist2[to] = dist2[u] + cost;
                if(!vis[to])
                {
                    q.push(to);
                    queuenum[to]++;
                    if(queuenum[to] >= n+m)
                        return;
                    vis[to] = true;
                }
            }
        }
    }
    return;
}
int main()
{
    int T, kases = 1;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d%d",&n,&m);
        for(int i=1; i<=m; i++)
        {
            int v,num,pt;
            scanf("%d%d",&v,&num);
            for(int j=0; j<num; j++)
            {
                scanf("%d",&pt);
                addedge(pt,i+n,v);
                addedge(i+n,pt,0);
            }
        }
        spfa1(1);
        spfa2(n);
        int maxcost = INF;
        for(int i=1; i<=n; i++)
        {
            int c = max(dist1[i],dist2[i]);
            if(c < maxcost)
                maxcost = c;
        }
        printf("Case #%d: ",kases++);
        if(maxcost == INF)
        {
            printf("Evil John\n");
            continue;
        }
        printf("%d\n",maxcost);
        bool flag = true;
        for(int i=1; i<=n; i++)
        {
            int c = max(dist1[i],dist2[i]);
            if(c == maxcost)
            {
                if(flag) printf("%d",i);
                else printf(" %d",i);
                flag = false;
            }
        }
        printf("\n");
    }
    return 0;
}