제출 #969807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969807		jadai007	Evacuation plan (IZhO18_plan)	C++14	100 / 100	366 ms	56044 KiB

plan

#include<bits/stdc++.h>

using namespace std;

struct graph{
    int u, w;
    bool operator<(const graph&d2)const{
        return w > d2.w;
    }
};

vector<pair<int, int>> vc[100100], tree[100100];
int n,m,u,v,w, k, dis[100100], pa[100100], parent[100100][20], dp[100100][20], depth[100100];
priority_queue<graph> pq;
vector<tuple<int, int, int>> f_edge, edge;

int fp(int n){
    if(pa[n] == n) return n;
    return pa[n] = fp(pa[n]);
}

void dfs(int u, int pa){
    for(auto x:tree[u]){
        int v = x.first, w = x.second;
        if(v == pa) continue;
        parent[v][0] = u;
        dp[v][0] = w;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

int cal(int u, int v){
    if(depth[u] > depth[v]) swap(u, v);
    int k = depth[v] - depth[u], mn = 1e9;
    for(int i = 0; i<=17; ++i){
        if(k&(1<<i)){
           mn = min(mn, dp[v][i]);
           v = parent[v][i];
        }
    }
    if(u == v) return mn;
    for(int i = 17; i>=0; --i){
        if(parent[u][i]!=parent[v][i]){
            mn = min({mn, dp[u][i], dp[v][i]});
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return min({mn, dp[u][0], dp[v][0]});
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1; i<=n; ++i) for(int j = 0; j<=17; ++j) dp[i][j] = 1e9;
    for(int i = 0; i<m; ++i){
        cin >> u >> v >> w;
        f_edge.emplace_back(u, v, w);
        vc[u].emplace_back(v, w);
        vc[v].emplace_back(u, w);
    }
    for(int i = 1; i<=n; ++i) dis[i] = 1e9;
    for(int i = 1; i<=n; ++i) pa[i] = i;
    cin >> k;
    for(int i = 1; i<=k; ++i){
        int u; cin >> u;
        dis[u] = 0;
        pq.push({u, dis[u]});
    }
    while(!pq.empty()){
        int u = pq.top().u, w = pq.top().w; pq.pop();
        if(dis[u] < w) continue;
        for(auto x:vc[u]){
            int v = x.first, ww = x.second;
            if(dis[v] > w+ww){
                dis[v] = w+ww;
                pq.push({v, dis[v]});
            }
        }
    }
    for(auto x:f_edge){
        int u = get<0>(x), v = get<1>(x);
        edge.emplace_back(min(dis[u], dis[v]), u, v);
    }
    sort(edge.begin(), edge.end());
    reverse(edge.begin(), edge.end());
    for(auto x:edge){
        int w = get<0>(x), u = get<1>(x), v = get<2>(x);
        if(fp(u)!=fp(v)){
            tree[u].emplace_back(v, w);
            tree[v].emplace_back(u, w);
            pa[fp(v)] = fp(u);
        }
    }
    dfs(1, -1);
    for(int j = 1; j<=17; ++j){
		for(int i = 1; i<=n; ++i){
			parent[i][j] = parent[parent[i][j-1]][j-1];
			dp[i][j] = min(dp[i][j-1], dp[parent[i][j-1]][j-1]);
		}
	}
    int q; cin >> q;
    while(q--){
        int u, v; cin >> u >> v;
        cout << cal(u, v) << '\n';
    }
}

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