Submission #868799

#	Time	Username	Problem	Language	Result	Execution time	Memory
868799		12345678	Evacuation plan (IZhO18_plan)	C++17	22 / 100	4025 ms	13780 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;
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];
        pq.push({dp[s], s});
        while (!pq.empty())
        {
            auto [cw, cl]=pq.top();
            pq.pop();
            for (auto [nl, nw]:d[cl]) if (min(dp[cl], mn[nl])>dp[nl]) dp[nl]=min(dp[cl], mn[nl]), pq.push({min(dp[cl], mn[nl]), nl});
        }
        cout<<dp[t]<<'\n';
    }
}

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