Submission #526451

#	Time	Username	Problem	Language	Result	Execution time	Memory
526451		azert9526	Evacuation plan (IZhO18_plan)	C++14	22 / 100	4072 ms	14420 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};

void getclosestnpp(int x)
{
    if(isnpp[x]) return;

    bool used[100005] = {0};
    priority_queue< pair<int, int> > pq;
    pq.push({0, x});
    while(!pq.empty())
    {
        int c = -pq.top().first, v = pq.top().second;
        pq.pop();
        if(isnpp[v])
        {
            cln[x] = c;
            return;
        }
        if(!used[v])
        {
            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;

    bool used[100005] = {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});
            }
        }
    }
}

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++)
    {
        int x;
        cin>>x;
        isnpp[x] = true;
    }

    for(int i = 1; i <= n; i++) getclosestnpp(i);

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

    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int solve(int, int)':
plan.cpp:45:38: warning: control reaches end of non-void function [-Wreturn-type]
   45 |     priority_queue< pair<int, int> > pq;
      |                                      ^~

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