Submission #138144

#	Time	Username	Problem	Language	Result	Execution time	Memory
138144		vardan__02	Evacuation plan (IZhO18_plan)	C++14	10 / 100	4059 ms	37652 KiB

plan

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
#define MP make_pair
#define PB push_back
const ll inf=100000000000;
ll n,m,i,j,k,u,v,w,a[100005],ans,dist[100005],color[100005],q,dist1[100005],t;
vector<pair<ll,ll> > graf[100005];
priority_queue<pair<ll,ll> > pq;
pair <ll,ll> p;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        graf[u].PB(MP(v,w));
        graf[v].PB(MP(u,w));
    }
    for(i=1;i<=n;i++)
        dist[i]=inf;
    cin>>k;
    for(i=1;i<=k;i++)
    {
        cin>>a[i];
        dist[a[i]]=0;
        pq.push(MP(0,a[i]));
    }
    for(i=1;i<=m;i++)
    {
        ll min_i=0;
        while(!pq.empty())
        {
            p=pq.top();
            pq.pop();
            if (!color[p.second])
			{
				min_i = p.second;
				break;
			}
        }
        color[min_i]=1;
        for(j=0;j<graf[min_i].size();j++)
        {
            ll h=graf[min_i][j].first;
            ll d=graf[min_i][j].second;
            if (!color[h] && dist[h] > dist[min_i]+d)
			{
				dist[h] = dist[min_i]+d;
				pq.push(MP(-dist[h], h));
			}
        }
    }
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>u>>v;
        ans=min(dist[u],dist[v]);
        t=0;
        for(j=1;j<=n;j++)
        {
            dist1[j]=dist[j];
            color[j]=0;
        }
        priority_queue<pair<ll,ll> > pq;
        pq.push(MP(dist1[u],u));
        for(ll l=1;l<=m;l++)
        {
            ll min_i=0;
            while(!pq.empty())
            {
                p=pq.top();
                pq.pop();
                if (!color[p.second])
                {
                    min_i = p.second;
                    break;
                }
            }
            if(min_i==v)
            {
                ans=min(ans,p.first);
                break;
            }
            color[min_i]=1;
            for(j=0;j<graf[min_i].size();j++)
            {
                ll h=graf[min_i][j].first;
                if (!color[h])
                {
                    dist1[h] = min(dist1[min_i],dist1[h]);
                    pq.push(MP(dist1[h], h));
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:59:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<graf[min_i].size();j++)
                 ~^~~~~~~~~~~~~~~~~~~
plan.cpp:102:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(j=0;j<graf[min_i].size();j++)
                     ~^~~~~~~~~~~~~~~~~~~

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