Submission #788534

#	Time	Username	Problem	Language	Result	Execution time	Memory
788534		acatmeowmeow	Crocodile's Underground City (IOI11_crocodile)	C++11	100 / 100	377 ms	89156 KiB

crocodile

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

using namespace std;

const int NMAX = 1e5;
long long dist[NMAX + 5][2];
vector<pair<int, long long>> adj[NMAX + 5];
//bool vis[NMAX + 5];
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 0; i < M; i++) {
        adj[R[i][0]].push_back({R[i][1], (long long)L[i]});
        adj[R[i][1]].push_back({R[i][0], (long long)L[i]});
    }

    for (int i = 0; i < N; i++) dist[i][0] = dist[i][1] = 1e18;

    for (int i = 0; i < K; i++) dist[P[i]][0] = dist[P[i]][1] = 0, pq.push({0, P[i]});

    while (pq.size()) {
        int p = pq.top().first, u = pq.top().second; pq.pop();
        if (p > dist[u][1]) continue;
		if (!u) return (int)p;
        for (auto&x : adj[u]) {
            int v = x.first;
		   	long long c = x.second;
			if (p + c < dist[v][0]) {
				if (dist[v][0] < dist[v][1]) pq.push({dist[v][0], v});
				dist[v][1] = dist[v][0];
				dist[v][0] = p + c;
			} else if (p + c < dist[v][1]) {
				dist[v][1] = p + c;
				pq.push({dist[v][1], v});
			}
        }
    }
    //for (int i = 0; i < N; i++) cout << dist[i][0] << " ";
    //return (int)dist[0][1];
}

/*#define MAX_N 50000
#define MAX_M 10000000

static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;

inline
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  //my_assert(3==scanf("%d %d %d",&N,&M,&K));
  cin >> N>> M >> K;
  for(i=0; i<M; i++)
    //my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
    cin >> R[i][0] >> R[i][1] >> L[i];
  for(i=0; i<K; i++)
    //my_assert(1==scanf("%d",&P[i]));
    cin >> P[i];
  //my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = travel_plan(N,M,R,L,K,P);
cout << ans << '\n';

  return 0;
}*/

Compilation message (stderr)

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

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