Submission #868810

#	Time	Username	Problem	Language	Result	Execution time	Memory
868810		12345678	Evacuation plan (IZhO18_plan)	C++17	41 / 100	4017 ms	19656 KiB

plan

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;
int n, m, u, v, w, k, x, q, s, t, mn[nx];
vector<pair<int, int>> d[nx];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
priority_queue<pair<int, int>> pq2;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
    for (int i=1; i<=n; i++) mn[i]=1e9;
    cin>>k;
    for (int i=1; i<=k; i++) cin>>x, mn[x]=0, pq.push({0, x});
    while (!pq.empty())
    {
        auto [cw, cl]=pq.top();
        pq.pop();
        for (auto [nl, nw]:d[cl]) if (cw+nw<mn[nl]) mn[nl]=cw+nw, pq.push({cw+nw, nl});
    }
    cin>>q;
    while (q--)
    {
        cin>>s>>t;
        vector<int> dp(n+1);
        dp[s]=mn[s];
        pq2.push({dp[s], s});
        while (!pq2.empty())
        {
            auto [cw, cl]=pq2.top();
            //cout<<"here"<<cl<<' '<<dp[cl]<<'\n';
            pq2.pop();
            for (auto [nl, nw]:d[cl]) if (min(dp[cl], mn[nl])>dp[nl]) dp[nl]=min(dp[cl], mn[nl]), pq2.push({min(dp[cl], mn[nl]), nl});
        }
        cout<<dp[t]<<'\n';
    }
}

/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

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