Submission #302668

#	Time	Username	Problem	Language	Result	Execution time	Memory
302668		shrek12357	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	678 ms	54636 KiB

crocodile

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include "crocodile.h"
using namespace std;

const long long INF = 1e10;
const int MAXN = 1e5+5;
#define ll long long

priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pair<ll , ll> dist[MAXN];
bool vis[MAXN];
vector<pair<int, int>> adjList[MAXN];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	for (int i = 0; i < m; i++) {
		adjList[r[i][0]].push_back({ r[i][1], l[i] });
		adjList[r[i][1]].push_back({ r[i][0], l[i] });
	}
	for (int i = 0; i < n; i++) {
		dist[i] = { INF, INF };
		vis[i] = false;
	}
	for (int i = 0; i < k; i++) {
		dist[p[i]] = { 0, 0 };
		pq.push({ 0, p[i] });
	}
	while (pq.size() > 0) {
		int cur = pq.top().second;
		int d = pq.top().first;
		pq.pop();
		if (vis[cur] || d != dist[cur].second) {
			continue;
		}
		if (cur == 0) {
			return d;
		}
		vis[cur] = true;
		for (auto i : adjList[cur]) {
			if (vis[i.first]) {
				continue;
			}
			if (d + i.second > dist[i.first].second) {
				continue;
			}
			if (d + i.second < dist[i.first].first) {
				dist[i.first].second = dist[i.first].first;
				dist[i.first].first = d + i.second;
			}
			else {
				dist[i.first].second = d + i.second;
			}
			pq.push({ d + i.second, i.first });
		}
	}
}

Compilation message (stderr)

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

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