제출 #684522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684522		mychecksedad	Evacuation plan (IZhO18_plan)	C++17	100 / 100	660 ms	103432 KiB

plan

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define MOD (1e9+7)
#define all(x) x.begin(), x.end()
const int N = 1e6, K = 20;


struct Dsu{
	vector<int> p, s;
	Dsu(int n){
		p.resize(n + 1);
		s.resize(n + 1);
		for(int i = 1; i <= n; ++i) p[i] = i, s[i] = 1;
	}
	int find(int v){
		if(p[v] == v) return v;
		return (p[v] = find(p[v]));
	}
	void merge(int a, int b){
		a = find(a);
		b = find(b);
		if(a != b){
			if(s[a] > s[b]) swap(a, b);
			p[a] = b;
			s[b] += s[a];
		}
	}
};

int n, m, k, dist[N], q, up[N][K], dp[N][K], dep[N];
vector<pair<int, int>> g[N], f[N];

void dfs(int v, int p){
	dep[v] = dep[p] + 1;
	up[v][0] = p;
	for(auto U: f[v]){
		int u = U.first, w = U.second;
		if(u != p){
			dfs(u, v);
			dp[u][0] = w;
		}
	}
}

void solve(){
	cin >> n >> m;
	for(int i = 0; i < m; ++i){
		int u, v, w; cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}

	for(int i = 1; i <= n; ++i) dist[i] = MOD;
	
	priority_queue<pair<int, int>> pq;
	cin >> k;
	for(int i = 1; i <= k; ++i){
		int v; cin >> v;
		pq.push({0, v});
		dist[v] = 0;
	}
	
	vector<bool> vis(n + 1);
	while(!pq.empty()){
		int v = pq.top().second; pq.pop();
		if(vis[v]) continue;
		vis[v] = 1;
		for(auto U: g[v]){
			int u = U.first, w = U.second;
			if(dist[u] > dist[v] + w){
				dist[u] = dist[v] + w;
				pq.push({-dist[u], u});
			}
		}
	}

	Dsu d(n);
	vector<array<int, 3>> edges;
	for(int i = 1; i <= n; ++i){
		for(auto U: g[i]){
			edges.pb({min(dist[i], dist[U.first]), i, U.first});
		}
	}
	sort(all(edges), greater<array<int, 3>>());

	for(auto e: edges){
		if(d.find(e[1]) != d.find(e[2])){
			d.merge(e[1], e[2]);
			f[e[1]].pb({e[2], e[0]});
			f[e[2]].pb({e[1], e[0]});
		}
	}

	for(int i = 1; i <= n; ++i) for(int j = 0; j < K; ++j) dp[i][j] = MOD;
	
	dep[1] = 0;
	dfs(1, 1);
	
	for(int j = 1; j < K; ++j){
		for(int i = 1; i <= n; ++i){
			up[i][j] = up[up[i][j - 1]][j - 1];
			dp[i][j] = min(dp[i][j - 1], dp[up[i][j - 1]][j - 1]);
		}
	}

	cin >> q;
	while(q--){
		int u, v, ans; cin >> u >> v;
		
		ans = min(dist[u], dist[v]);	

		if(dep[u] > dep[v]) swap(u, v);

		for(int j = K - 1; j >= 0; --j){
			if((dep[v] - dep[u])&(1<<j)){
				ans = min(ans, dp[v][j]);
				v = up[v][j];
			}
		}
		for(int j = K - 1; j >= 0; --j){
			if(up[v][j] != up[u][j]){
				ans = min({ans, dp[u][j], dp[v][j]});
				u = up[u][j];
				v = up[v][j];
			}
		}

		if(u != v)
			ans = min(ans, dp[u][0]);

		cout << ans << '\n';
	}
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	solve();
	return 0;
}

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