Submission #1140188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140188		Agageldi	Evacuation plan (IZhO18_plan)	C++20	10 / 100	4091 ms	17600 KiB

plan

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 200006
#define pb push_back
#define ff first
#define ss second
#define sz(s) (int)s.size()
#define all(x) x.begin(),x.end()
#define pii pair<int,int>

int n,dp[N], dis[N], k, t, m, q, answer, vis[N], tr;
priority_queue <pii> p;
vector <pii> v[N];

void solve(int x,int y,int val) {
	if(dp[x] >= val) {
		answer = max(answer,val);
		return;
	}
	dp[x] = val;
	if(x == y) {
		answer = max(answer,val);
		return;
	}
	vis[x] = 1;
	for(auto i : v[x]) {
		if(vis[i.ff]) continue;
		solve(i.ff,y,min(val,dis[i.ff]));
	}
}

int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i = 1;i<=n;i++) {
		dis[i] = INT_MAX;
	}
	for(int i = 1; i <= m; i++) {
		int x, y, lentgh;
		cin >> x >> y >> lentgh;
		v[x].pb({y,lentgh});
		v[y].pb({x,lentgh});
	}
	cin >> k;
	for(int i = 1; i <= k; i++) {
		int x;
		cin >> x;
		dis[x] = 0;
		p.push({0, x});
	}
	while(!p.empty()) {
		int val = p.top().ss;
		p.pop();
		for(auto i : v[val]) {
			if(dis[i.ff] <= dis[val] + i.ss) continue;
			dis[i.ff] = dis[val] + i.ss;
			p.push({(-1) * dis[i.ff],i.ff});
		}
	}
	cin >> q;
	for(int i = 1;i <= q; i++) {
		int x, y;
		cin >> x >> y;
		answer = 0;
		memset(vis,0,sizeof vis);
		memset(dp,0,sizeof dp);
		solve(x,y,dis[x]);
		cout << answer << '\n';		
	}
}

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