Submission #697613

#	Time	Username	Problem	Language	Result	Execution time	Memory
697613		vjudge1	Evacuation plan (IZhO18_plan)	C++17	0 / 100	156 ms	16868 KiB

plan

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
 
#define file ""
 
#define all(x) x.begin(), x.end()
 
#define fr first
#define sc second
 
#define pb push_back
                                                         
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5;
const int inf = 1e9 + 5;

set <pii> s;
vector <pii> g[N];
int v [N], npp [N], d[N];

int main(){
  

	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	srand(time(NULL));
	int n, m, k, q;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		g[x].pb({y, w});
		g[y].pb({x, w});
	}
	for (int i = 1; i <= n; i++) {
		d[i] = inf;
	}
	cin >> k;
	for (int i = 1; i <= k; i++) {
		cin >> v[i];
		d[v[i]] = 0;
		s.insert({0, v[i]});
		npp[v[i]] = 1;
	}
	while(!s.empty()) {
		pii temp = *s.begin();
		int x = temp.sc;
		s.erase(s.begin());
		for (pii u : g[x]) {
			int to = u.fr;
			int weight = u.sc;
			if (d[to] > d[x] + weight) {
				s.erase({d[to], to});
				d[to] = d[x] + weight;
				s.insert({d[to], to});
			}				
		}
	}

	cin >> q;

	while (q--) {
		int start, finish;
		cin >> start >> finish;	
		cout << max(d[start], d[finish]) << "\n";
	}
}

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