제출 #1140197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140197		Agageldi	Evacuation plan (IZhO18_plan)	C++17	10 / 100	4091 ms	31116 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>

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

bool check(int val,int x,int y) {
	queue <int> d;
	d.push(x);
	dp[x] = dis[x];
	while(!d.empty()) {
		int a = d.front();
		d.pop();
		for(auto i : v[a]) {
			if(dis[i.ff] < val || dp[i.ff] >= min(dis[i.ff],dp[a])) continue;
			dp[i.ff] = min(dp[a],dis[i.ff]);
			d.push(i.ff);
		}
	}
	if(dp[y] >= val) return 1;
	return 0;
}

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;
		dp.clear();
		if(x > y) swap(x,y);
		int l = 0, r = 1e8, jog = 0;
		while(l <= r) {
			int md = (l + r) / 2;
			if(md > dis[x]) {
				r = md - 1;
				continue;
			}
			if(dp[y] >= md || check(md,x,y) == 1) {
				l = md + 1;
				jog = md;
			}
			else r = md-1;
		}
		cout << jog << '\n';
	}
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

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