제출 #684548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684548		OrazB	Evacuation plan (IZhO18_plan)	C++14	54 / 100	1314 ms	41156 KiB

plan

#include <bits/stdc++.h>
#define N 100005
#define wr cout << "Continue debugging\n";
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <ll, ll>
#define pb push_back
#define ff first
#define ss second
using namespace std;

ll dis[N], len[N], num[N];
vector<pii> E[N];

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int u, v, w;
		cin >> u >> v >> w;	
		E[u].pb({v, w});
		E[v].pb({u, w});
	}
	for (int i = 1; i <= n; i++){
		dis[i] = 1e18;
	}
	priority_queue<pii, vector<pii>, greater<pii>> q;
	int k;
	cin >> k;
	while(k--){
		int x;
		cin >> x;
		q.push({0, x});
		dis[x] = 0;
	}
	while(!q.empty()){
		int x = q.top().ss;
		q.pop();
		for (auto i : E[x]){
			if (dis[i.ff] > dis[x]+i.ss){
				dis[i.ff] = dis[x]+i.ss;
				q.push({i.ss, i.ff});
			}
		}
	}
	int qqq;
	cin >> qqq;
	int old = qqq;
	while(qqq--){
		int u, v;
		cin >> u >> v;
		if (n <= 15 or old == 1){
			ll l = 0, r = dis[u], ans = dis[u];
			while(l <= r){
				ll md = (l+r)/2;
				for (int i = 1; i <= n; i++){
					len[i] = 1e18;
				}
				len[u] = 0;
				queue<ll> qq;
				qq.push(u);
				while(!qq.empty()){
					int x = qq.front();
					qq.pop();
					for (auto i : E[x]){
						if (len[i.ff] > len[x]+i.ss and dis[i.ff] >= md){
							len[i.ff] = len[x]+i.ss;
							qq.push(i.ff);
						}
					}
				}
				if (len[v] == 1e18) r = md - 1;
				else{
					ans = md;
					l = md + 1;
				}
			}
			cout << ans << '\n';
		}else cout << min(dis[u], dis[v]) << '\n';
	}
}	

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