HDU - 5521 巧妙地最短路-蒲公英云

HDU - 5521 巧妙地最短路

迷南。 2022-05-08 08:38 224阅读 0赞

题意：n个点，m块，块的意思就是说，在块中的点任意两点的距离都是t，问分别从1点和n点走到某个点，这个点的花费就是二者较大的，问这n个点花费最小是多少，并按字典序打印序号

思路：这题头疼的就是不知道怎么建图，暴力建图会超内存，有一个巧妙的方法是

将这个块中的点全部连到一个点上，每条边花费t/2，这样任意两点仍然是t的花费。

这样最多1e6条边

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
const ll INF=99999999999999999;
struct node{
    int v;
    ll w;
};
vector<node> G[N];
ll dis1[N], dis2[N], dis[N];
int n, m;
int ans[N], tot;
bitset<N> inq;
void spfa(int s, ll dd[]){
    for(int i=1; i<=n+m; i++) dd[i]=INF;
    inq.reset();
    dd[s]=0;
    queue<int> q; q.push(s); inq[s]=1;
    while(!q.empty()){
        int u=q.front(); q.pop();
        inq[u]=0;
        for(int i=0; i<G[u].size(); i++){
            int v=G[u][i].v;
            ll w=G[u][i].w;
            if(dd[v]>dd[u]+w){
                dd[v]=dd[u]+w;
                if(!inq[v]){
                    inq[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
void init(){
    for(int i=1; i<=n+m; i++){
        G[i].clear();
    }
}
int main(){
    int T, cas=0;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        init();
        for(int i=1; i<=m; i++){
            int ti, si;
            scanf("%d%d", &ti, &si);
            for(int j=1; j<=si; j++){
                int p;
                scanf("%d", &p);
                G[n+i].push_back((node){p, ti});
                G[p].push_back((node){n+i, ti});
            }
        }
        spfa(1, dis1);
        spfa(n, dis2);
        ll mn=INF;
        for(int i=1; i<=n; i++){
            dis[i]=max(dis1[i], dis2[i]);
            mn=min(dis[i], mn);
        }
        printf("Case #%d: ", ++cas);
        if(mn==INF){
            printf("Evil John\n");
            continue;
        }
        printf("%lld\n", mn/2);
        tot=0;
        for(int i=1; i<=n; i++){
            if(mn==dis[i])
                ans[++tot]=i;
       //     printf("%lld ", dis[i]);
        }
       // puts("");
        for(int i=1; i<=tot; i++){
            printf("%d", ans[i]);
            if(i==tot) putchar('\n');
            else  putchar(' ');
        }
    }
    return 0;
}