Submission #644055

#	Time	Username	Problem	Language	Result	Execution time	Memory
644055		ToroTN	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	2 ms	2644 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define X first
#define Y second
vector<pair<ll,ll> > g[100005];
ll n,m,u_i,v_i,w_i,d[100005],u,y,cost,k,p[100005],pin,ans;
priority_queue<pair<ll,ll> > pq;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n=N;
    m=M;
    k=K;
    for(int i=0;i<k;i++)
    {
        p[i+1]=P[i]+1;
    }
    for(int i=0;i<m;i++)
    {
        u_i=R[i][0]+1;
        v_i=R[i][1]+1;
        w_i=L[i];
        g[u_i].pb({w_i,v_i});
        g[v_i].pb({w_i,u_i});
    }
    for(int i=1;i<=n;i++)
    {
        sort(g[i].begin(),g[i].end());
        d[i]=2e9;
    }
    d[1]=0;
    pq.push({0,1});
    while(!pq.empty())
    {
        u=pq.top().second;
        pq.pop();
        pin=0;
        for(int i=0;i<g[u].size();i++)
        {
            cost=g[u][i].X;
            y=g[u][i].Y;
            if(d[u]+cost<d[y])
            {
                if(pin==0)
                {
                    pin=1;
                }else
                {
                    d[y]=d[u]+cost;
                    pq.push({-d[y],y});
                }
            }
        }
    }
    ans=2e9;
    for(int i=1;i<=k;i++)
    {
        ans=min(ans,d[p[i]]);
    }
    return ans;
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i=0;i<g[u].size();i++)
      |                     ~^~~~~~~~~~~~

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11