Submission #526456

#	Time	Username	Problem	Language	Result	Execution time	Memory
526456		azert9526	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4096 ms	29984 KiB

plan

#include <bits/stdc++.h>

#define ll long long
#define MOD 1000000007

using namespace std;

int n, m, k;
vector< pair<int, int> > g[100005];
bool isnpp[100005] = {0};
int cln[100005] = {0}, npp[100005] = {0};
bool used[100005] = {0};

void getclosestnpp()
{
    priority_queue< pair<int, int> > pq;
    for(int i = 0; i < k; i++)
    {
        pq.push({0, npp[i]});
    }
    while(!pq.empty())
    {
        int c = -pq.top().first, v = pq.top().second;
        pq.pop();
        if(!used[v])
        {
            cln[v] = c;
            used[v] = true;
            for(pair<int, int> u : g[v])
            {
                if(!used[u.first]) pq.push({-c-u.second, u.first});
            }
        }
    }
}

int solve(int s, int t)
{
    if(isnpp[s] || isnpp[t]) return 0;

    for(int i = 1; i <= n; i++) used[i] = 0;
    priority_queue< pair<int, int> > pq;
    pq.push({cln[s], s});
    while(!pq.empty())
    {
        int d = pq.top().first, v = pq.top().second;
        pq.pop();
        if(v == t)
        {
            return d;
        }
        if(!used[v])
        {
            used[v] = true;
            for(pair<int, int> u : g[v])
            {
                if(!used[u.first]) pq.push({min(d, cln[u.first]), u.first});
            }
        }
    }

    return -1;
}

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

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

    cin>>k;
    for(int i = 0; i < k; i++)
    {
        cin>>npp[i];
        isnpp[npp[i]] = true;
    }

    getclosestnpp();

    int q;
    cin>>q;
    for(int i = 0; i < q; i++)
    {
        int s, t;
        cin>>s>>t;
        cout<<solve(s, t)<<'\n';
    }

    return 0;
}

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