This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
const int N = 100000 + 7;
const int INF = (int) 1e9 + 7;
int n, m, k, best[N];
vector<pair<int, int>> lol[N];
vector<pair<int, int>> g[N];
priority_queue<pair<int, int>> q;
int lt[N], step;
void push(int i, int value) {
for (auto &it : g[i]) {
lol[it.first].push_back({min(INF, value + it.second), i});
sort(lol[it.first].begin(), lol[it.first].end());
step++;
vector<pair<int, int>> lol2;
for (auto &k : lol[it.first]) {
if (lt[k.second] != step) {
lol2.push_back(k);
lt[k.second] = step;
if ((int) lol2.size() == 2) {
break;
}
}
}
lol[it.first] = lol2;
}
best[i] = value;
q.push({-best[i], i});
}
int get_second(int a) {
if ((int) lol[a].size() < 2) {
return INF;
}
return lol[a][1].first;
}
int travel_plan(int nn, int mm, int r[][2], int len[], int kk, int ch[]) {
n = nn;
m = mm;
k = kk;
for (int i = 0; i < n; i++) {
g[i].clear();
lol[i].clear();
best[i] = INF;
}
for (int i = 0; i < m; i++) {
g[r[i][0]].push_back({r[i][1], len[i]});
g[r[i][1]].push_back({r[i][0], len[i]});
lol[r[i][0]].push_back({INF, r[i][1]});
lol[r[i][1]].push_back({INF, r[i][0]});
}
for (int i = 0; i < k; i++) {
push(ch[i], 0);
}
while (!q.empty()) {
int a = q.top().second, o = -q.top().first;
q.pop();
if (best[a] != o) {
continue;
}
for (auto &it : g[a]) {
int node = it.first, relax = get_second(node);
if (relax < best[node]) {
push(node, relax);
}
}
}
if (best[0] == INF) {
best[0] = -1;
}
return best[0];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |