제출 #339296

#제출 시각아이디문제언어결과실행 시간메모리
339296Dilshod_ImomovEvacuation plan (IZhO18_plan)C++17
100 / 100
1140 ms189036 KiB
# include <bits/stdc++.h> # define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) # define int long long # define fi first # define se second using namespace std; const int N = 2e6 + 7; const int mod = 1e9 + 7; vector < pair < int, int > > adj[N]; int dist[N], n, m, go, pr[N], ans[N], sz[N]; bool used[N]; set < int > st[N]; int find_set( int a ) { if ( a == pr[a] ) { return a; } return find_set(pr[a]); } void merge( int a, int b, int val ) { int x = find_set(a); int y = find_set(b); if ( x == y ) { return; } if ( sz[x] < sz[y] ) { swap( x, y ); } for ( auto i: st[y] ) { if ( st[x].count(i) ) { ans[ i ] = val; } else { st[x].insert(i); } } st[y].clear(); pr[y] = x; sz[x] += sz[y]; } int32_t main() { speed; cin >> n >> m; for ( int i = 1; i <= m; i++ ) { int u, v, w; cin >> u >> v >> w; adj[u].push_back( { v, w } ); adj[v].push_back( { u, w } ); } for ( int i = 1; i <= n; i++ ) { dist[i] = 1e12; pr[i] = i; sz[i] = 1; } int k; cin >> k; set < pair < int, int > > q; for ( int i = 1; i <= k; i++ ) { int x; cin >> x; q.insert( { 0, x } ); dist[x] = 0; } while ( !q.empty() ) { int v = q.begin()->se; q.erase( q.begin() ); for ( auto pr: adj[v] ) { int u = pr.fi, w = pr.se; if ( dist[u] > dist[v] + w ) { q.erase( { dist[u], u } ); dist[u] = dist[v] + w; q.insert( { dist[u], u } ); } } } int qr; cin >> qr; for ( int i = 1; i <= qr; i++ ) { int x, y; cin >> x >> y; st[x].insert(i); st[y].insert(i); } vector < pair < int, int > > vc; for ( int i = 1; i <= n; i++ ) { vc.push_back( { dist[i], i } ); } sort( vc.rbegin(), vc.rend() ); for ( int i = 0; i < n; i++ ) { int x = vc[i].se; used[x] = 1; // cout << x << endl; for ( auto pr: adj[x] ) { int u = pr.fi; if ( used[u] ) { merge( x, u, dist[x] ); } } } for ( int i = 1; i <= qr; i++ ) { cout << ans[i] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...