Submission #595107

#	Time	Username	Problem	Language	Result	Execution time	Memory
595107		Bench0310	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	518 ms	71276 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"

using namespace std;
typedef long long ll;

int travel_plan(int n,int m,int r[][2],int l[],int k,int p[])
{
    vector<array<int,2>> v[n];
    for(int i=0;i<m;i++)
    {
        int a=r[i][0],b=r[i][1];
        int c=l[i];
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    priority_queue<array<int,2>,vector<array<int,2>>,greater<>> q;
    vector<int> vis(n,0);
    for(int i=0;i<k;i++) for(int j=0;j<2;j++) q.push({0,p[i]});
    const int lim=1000000000;
    while(!q.empty())
    {
        auto [d,a]=q.top();
        q.pop();
        if((++vis[a])!=2) continue;
        if(a==0) return d;
        for(auto [to,c]:v[a]) if(d+c<=lim) q.push({d+c,to});
    }
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
   29 | }
      | ^

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