제출 #1133202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133202		Halym2007	Evacuation plan (IZhO18_plan)	C++17	41 / 100	4094 ms	25320 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e5 + 5;

int l1, r1, n, m, k, a[N];
int vis1[N], vis[N], dis[N];
priority_queue <pii, vector <pii>, greater<pii>> q;
vector <pii> v[N];

void dfs (int x, int y) {
	if (dis[x] < y) return;
	vis[x] = 1;
	for (pii i : v[x]) {
		if (vis[i.ff] or dis[i.ff] < y) continue;
		dfs (i.ff, y);
	}	
}

int check (int x) {
	dfs (l1, x);
	int ret = 0;
	if (vis[r1]) ret = 1;
	for (int i = 1; i <= n; ++i) {
		vis[i] = 0;
	}
	return ret;
}

int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int l, r, w;
		cin >> l >> r >> w;
		v[l].pb ({r, w});
		v[r].pb ({l, w});
	}
	cin >> k;
	for (int i = 1; i <= n; ++i) {
		dis[i] = 1e9;
	}
	for (int i = 1; i <= k; ++i) {
		cin >> a[i];
		q.push({0, a[i]});
		dis[a[i]] = 0;
	}
	
	while (!q.empty()) {
		int x = q.top().ss;
		q.pop();
		if (vis1[x]) continue;
		vis1[x] = 1;
		for (pii i : v[x]) {
			if (dis[i.ff] > dis[x] + i.ss) {
				dis[i.ff] = dis[x] + i.ss;
				q.push({dis[i.ff], i.ff});
			}
		}
	}
	int q1;
	cin >> q1;
	while ( q1-- ) {
		cin >> l1 >> r1;
		int l = 1, r = 1e8, jog = 0;
		while (l <= r) {
			int md = (l + r) / 2;
			if (check (md)) {
				l = md + 1;
				jog = md;
			}
			else {
				r = md - 1;
			}
		}
		cout << jog << "\n";
	}
}

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