Submission #138121

#	Time	Username	Problem	Language	Result	Execution time	Memory
138121		vardan__02	Evacuation plan (IZhO18_plan)	C++14	23 / 100	780 ms	32644 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;
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;
        cout<<min(dist[u],dist[v])<<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++)
                 ~^~~~~~~~~~~~~~~~~~~

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