| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 995993 | 54skyxenon | Crocodile's Underground City (IOI11_crocodile) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// https://oj.uz/problem/view/IOI11_crocodile
/** Needed for linking!!! */
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF (ll)1e18
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
vector<map<int, int>> graph(N);
vector<set<int>> visited(N);
for (int i = 0; i < M; i++) {
int u = R[i][0];
int v = R[i][1];
graph[u][v] = graph[v][u] = L[i];
}
// Run Dijkstra's and only care about the second best distance, propagated downwards
vector<vector<ll>> dist(graph.size(), {INF, INF});
priority_queue<pair<ll, ll>> pq;
for (int& p : P) {
pq.push({0, p});
dist[p][0] = dist[p][1] = 0;
}
while (pq.size()) {
auto [d, u] = pq.top();
pq.pop();
d = -d;
if (d > dist[u][1]) {
continue;
}
// Thank you to sreepranad Devarakonda from USACO Guide
for (auto& [v, w] : graph[u]) {
ll cost = w + d;
if (cost < dist[v][0]) {
if (dist[v][0] != dist[v][1] && dist[v][0] < INF) {
dist[v][1] = dist[v][0];
pq.push({-dist[v][1], v});
}
dist[v][0] = cost;
}
else if (cost < dist[v][1]) {
dist[v][1] = cost;
pq.push({-cost, v});
}
}
}
return dist[0][1];
}