【dij变形】牛客练习赛93 C

快来打我* 2024-03-17 18:49 41阅读 0赞

[C-点权\_牛客练习赛93 (nowcoder.com)][C-_93 _nowcoder.com]

题意：

![12bb6ebbe330486085e937cbec98e25a.png][]

![cee60d41e6204445a7b9149a03904a74.png][]

思路：

重要的是在松弛的时候要满足什么条件才开始松弛

这里是用两个点来松弛一个点

![8731658361ef40bdb50eaaaebe1e99ff.png][]

Code：

#include <bits/stdc++.h>
     
    //#define int long long
     
    using namespace std;
     
    const int mxn=1e5+10;
    const int mxv=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    struct ty{
        int to,next,w;
    }edge[mxe<<2];
    
    struct ty2{
        int x,dis;
        bool operator<(const ty2&oth)const{
            return oth.dis<dis;
        }
    };
    
    multiset<int> S[mxn];
    
    priority_queue<ty2> Q;
    
    int N,u,v,w;
    int tot=0;
    int head[mxn],in[mxn];
    int vis[mxn],dis[mxn];
    
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=N;i++) head[i]=-1;
    }
    int get(int u){
        return (*S[u].begin())+(*(++S[u].begin()));
    }
    void dij(){
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=N;i++){
            if(in[i]<=1){
                Q.push({i,0});
                dis[i]=0;
            }
            S[i].insert(Inf);
            S[i].insert(Inf);
        }
        while(!Q.empty()){
            auto u=Q.top();
            Q.pop();
            if(vis[u.x]) continue;
            vis[u.x]=1;
            for(int i=head[u.x];~i;i=edge[i].next){
                S[edge[i].to].insert(dis[u.x]+edge[i].w);
                if(dis[edge[i].to]>get(edge[i].to)){
                    dis[edge[i].to]=get(edge[i].to);
                    if(!vis[edge[i].to]) Q.push({edge[i].to,dis[edge[i].to]});
                }
            }
        }
    }
    void solve(){
        cin>>N;
        G_init();
        for(int i=1;i<=N-1;i++){
            cin>>u>>v>>w;
            add(u,v,w);
            add(v,u,w);
            in[u]++;
            in[v]++;
        }
        dij();
        for(int i=1;i<=N;i++){
            if(dis[i]==Inf) cout<<-1<<" \n"[i==N];
            else cout<<dis[i]<<" \n"[i==N];
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[C-_93 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/11183/C
[12bb6ebbe330486085e937cbec98e25a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f3e20fa65d034a588f7ad71c80f30533.png
[cee60d41e6204445a7b9149a03904a74.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/986d3c4568ce4d88b907cbcfb13a7f24.png
[8731658361ef40bdb50eaaaebe1e99ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5b78613d191543768aada3518579e744.png