DFS

 avatar
unknown
c_cpp
2 years ago
781 B
4
Indexable
// DFS
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e6+5;
vector<pair<int, int>> g[MAXN];
int vis[MAXN];
long long dis[MAXN];

void dfs(int v, long long d){
    vis[v] = 1;
    dis[v] = d;
    for(auto i : g[v]){
        if(!vis[i.first]){
            dfs(i.first, d + i.second);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    for(int i=0;i<n-1;i++){
        int u,v,b;
        cin >> u >> v >> b;
        g[u].push_back({v, b});
        g[v].push_back({u, b});
    }
    
    dfs(1, 0);

    for(int i=1;i<=n;i++){
        if(g[i].size() <= 1){
            cout << "City " << i << ": " << dis[i] << "\n";
        }
    }

    return 0;
}
Editor is loading...