제출 #968768

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
968768		tamir1	Evacuation plan (IZhO18_plan)	C++17	35 / 100	4041 ms	46016 KiB

plan

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
ll n,m,k,i,x,y,z,q,dis[100005],mx,dis2[100005];
bitset<100005> vis;
vector<pair<ll,ll>> v[100005];
priority_queue<pair<ll,ll>> a;
void dfs(ll x,ll y,ll d){
	if(vis[x]) return;
	if(x==y){
		mx=max(mx,d);
		return;
	}
	if(mx>=d) return;
	vis[x]=1;
	for(pair<ll,ll> i:v[x]){
		dfs(i.ff,y,min(d,dis[i.ff]));
	}
	vis[x]=0;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(i=1;i<=m;i++){
		cin >> x >> y >> z;
		v[x].push_back({y,z});
		v[y].push_back({x,z});
	}
	cin >> k;
	for(i=1;i<=k;i++){
		cin >> x;
		a.push({0,x});
	}
	while(!a.empty()){
		z=a.top().ff;
		x=a.top().ss;
		a.pop();
		if(vis[x]) continue;
		vis[x]=1;
		dis[x]=-z;
		for(pair<ll,ll> i:v[x]){
			if(!vis[i.ff]) a.push({z-i.ss,i.ff});
		}
	}
	vis.reset();
	cin >> q;
	for(i=1;i<=q;i++){
		cin >> x >> y;
		if(n<=15){
			mx=0;
			dfs(x,y,min(dis[x],dis[y]));
			cout << mx << "\n";
		}
		else if(q==1){
			a.push({-dis[x],x});
			while(!a.empty()){
				z=-1*a.top().ff;
				x=a.top().ss;
				if(vis[x]) continue;
				vis[x]=1;
				dis2[x]=z;
				for(pair<ll,ll> i:v[x]){
					if(!vis[i.ff]) a.push({-1*min(z,dis[i.ff]),i.ff});
				}
			}
			cout << dis2[y] << "\n";
		}
		else{
			cout << min(dis[x],dis[y]) << "\n";
		}
	}
}

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