제출 #334007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
334007		limabeans	Evacuation plan (IZhO18_plan)	C++17	100 / 100	678 ms	62212 KiB

plan

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll inf = 1e18;

const int maxn = 1e5 + 5;



int n, m, k;
vector<pair<ll,int>> g[maxn];
vector<pair<ll,pair<int,int>>> edges;

vector<int> a;

ll dist[maxn];

void dijk() {
    for (int i=1; i<=n; i++) {
	dist[i] = inf;
    }
    priority_queue<pair<ll,int>> pq;
    for (int x: a) {
	dist[x] = 0;
	pq.push({0, x});
    }

    while (pq.size()) {
	auto cur = pq.top();
	pq.pop();
	ll d = -cur.first;
	int at = cur.second;
	if (d > dist[at]) continue;

	for (auto ed: g[at]) {
	    int to = ed.second;
	    ll walk = d + ed.first;
	    if (walk < dist[to]) {
		dist[to] = walk;
		pq.push({-dist[to],to});
	    }
	}
    }
}


int par[maxn];

vector<int> nodes[maxn];
vector<pair<ll,int>> trans[maxn];



void join(int u, int v, ll wei) {
    u = par[u];
    v = par[v];
    if (u == v) return;

    if (nodes[u].size()<nodes[v].size()) {
	swap(u,v);
    }

    while (nodes[v].size()) {
	int cur = nodes[v].back();
	nodes[v].pop_back();

	trans[cur].push_back({wei,u});
	nodes[u].push_back(cur);
	par[cur] = u;
    }
    
}


ll solve(int u, int v) {
    if (trans[u].size()>trans[v].size()) {
	swap(u,v);
    }

    int ulen = trans[u].size();
    int vlen = trans[v].size();
    int ans = 0;
    for (int i=1; i<=ulen; i++) {
	if (trans[u][ulen-i].second != trans[v][vlen-i].second) {
	    break;
	}
	ans = min(trans[u][ulen-i].first, trans[v][vlen-i].first);
    }

    return ans;
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

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

    cin>>k;
    a.resize(k);
    for (int i=0; i<k; i++) {
	cin>>a[i];
    }

    dijk();

    for (auto &ed: edges) {
	int u = ed.second.first;
	int v = ed.second.second;
	ed.first = min(dist[u],dist[v]);
    }



    //dsu edges from hi to lo
    sort(edges.rbegin(), edges.rend());

    for (int i=1; i<=n; i++) {
	par[i]=i;
	nodes[i].push_back(i);
	trans[i].push_back({inf,i});
    }

    for (auto ed: edges) {
	int u = ed.second.first;
	int v = ed.second.second;
	join(u,v,ed.first);
    }


    int q;
    cin>>q;
    while (q--) {
	int u,v;
	cin>>u>>v;
	cout<<solve(u,v)<<"\n";
    }
    
    
    return 0;
}

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