AT_abc373_d 题解

ikunTLE · 2024-10-01 11:26:43 · 题解

题目传送门

思路

如果确定了一个顶点的值，相邻顶点的值确定。由于该图的连通性，只要任意一点上的值确定，所有的值都会根据该点得知而确定。

因此，可以给初始的顶点赋值为 0，BFS 确定其连通的值。

注意事项

• 不开 long long 见祖宗。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=2e5+10;
struct node{
    int v,w;
};vector<node>vc[N];
bool vis[N];
int ans[N];
signed main(){
    int n=read(),m=read();
    while(m--){
        int u=read(),v=read(),w=read();
        vc[u].push_back({v,w});
        vc[v].push_back({u,-w});
    }
    for(int i=1;i<=n;++i){
        if(vis[i])
            continue;
        queue<int>q;
        q.push(i),vis[i]=true;
        while(!q.empty()){
            int u=q.front();
            for(auto i:vc[u])
                if(!vis[i.v]){
                    vis[i.v]=true;
                    ans[i.v]=ans[u]+i.w;
                    q.push(i.v);
                }
            q.pop();
        }
    }
    for(int i=1;i<=n;++i)
        printf("%lld ",ans[i]);
    printf("\n");
    return 0;
}