Submission #995674

#	Time	Username	Problem	Language	Result	Execution time	Memory
995674		Acanikolic	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4054 ms	31904 KiB

plan

#include <bits/stdc++.h>  

#define pb push_back
 
#define F first
 
#define S second
 
using namespace std;
 
const int N = 1e5 + 10;
 
const int mod = 998244353;
 
const int inf = 1e9;
 
vector<pair<int,int>>g[N]; 
bool mark[N]; 
long long dist[N];
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
 	int n,m;
 	cin >> n >> m;
 	for(int i = 1; i <= n; i++) dist[i] = inf;
 	for(int i = 1; i <= m; i++) {
 		int u,v,w;
 		cin >> u >> v >> w;
 		g[u].pb({v,w});
 		g[v].pb({u,w});
 	}
 	int k;
 	cin >> k;
 	priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pq;
 	for(int i = 1; i <= k; i++) {
 		int x;
 		cin >> x;
 		mark[x] = true;
 		pq.push({0,x});
 		dist[x] = 0;
 	}
 	while(!pq.empty()) {
 		long long dst = pq.top().F;
 		int u = pq.top().S;
 		pq.pop();
 		for(auto X : g[u]) {
 			if(dist[X.F] > dst + X.S) {
 				dist[X.F] = dst + X.S;
 				pq.push({dist[X.F],X.F});
 			}
 		}
 	}
 	int q;
 	cin >> q;
 	while(q--) {
 		int u,v;
 		cin >> u >> v;
		queue<int>q;
		q.push(u);
		vector<bool>was(n + 1,false);
		vector<long long>mn(n + 1,0);
		mn[u] = dist[u];
		while(!q.empty()) {
			int s = q.front();
			was[s] = true;
			q.pop();
			for(auto X : g[s]) {
				if(min(mn[s],dist[X.F]) > mn[X.F]) {
					mn[X.F] = min(mn[s],dist[X.F]);
					q.push(X.F);
				}
			}
		}
		cout << mn[v] << "\n";
 	}
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46