Submission #1031887

#TimeUsernameProblemLanguageResultExecution timeMemory
1031887Khanhcsp2Sightseeing (NOI14_sightseeing)C++14
25 / 25
1808 ms262144 KiB
#include<bits/stdc++.h> #define el '\n' #define fi first #define sc second #define int ll #define pii pair<int, int> #define all(v) v.begin(), v.end() using namespace std; using ll=long long; using ull=unsigned long long; using ld=long double; const int mod=1e9+7; const int N=5e5+11; int pa[N], n, q, m, dis[N]; vector<pii> adj[N]; struct eg { int u, v, w; }; vector<eg> e; bool cmp(eg x, eg y) { return x.w > y.w; } int lead(int u) { if(pa[u]==u) return u; return pa[u]=lead(pa[u]); } void dfs(int u, int pa) { for(auto v:adj[u]) { if(v.fi!=pa) { dis[v.fi]=min(dis[u], v.sc); dfs(v.fi, u); } } } void sol() { cin >> n >> m >> q; for(int i=1;i<=m;i++) { int u, v, w; cin >> u >> v >> w; e.push_back({u, v, w}); } sort(all(e), cmp); for(int i=1;i<=n;i++) pa[i]=i, dis[i]=1e18; for(auto x:e) { int u=lead(x.u), v=lead(x.v); if(u!=v) { pa[u]=v; adj[x.u].push_back({x.v, x.w}); adj[x.v].push_back({x.u, x.w}); } } dfs(1, 0); while(q--) { int u; cin >> u; if(u==1) cout << 0 << el; else cout << dis[u] << el; } } signed main() { // freopen("divisor.INP", "r", stdin); // freopen("divisor.OUT", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); int t=1; //cin >> t; while(t--) { sol(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...