HDU - 5521 巧妙地最短路

迷南。 2022-05-08 08:38 245阅读 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;
    }