DFS
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...