#include "crocodile.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 1;
const ll inf = 1e9;
vector<pair<int, int>> g[N]; //init me
ll res[N];
pair<int, int> rf[N];
void dijkstra(int st) {
for (int i = 0; i < N; i++) {
rf[i] = {-1, -1};
res[i] = inf;
}
res[st] = 0;
priority_queue<pair<int, int>> nxt;
nxt.push({-res[st], st});
while (!nxt.empty()) {
int cur = nxt.top().second;
int cost = -nxt.top().first;
nxt.pop();
if (cost != res[cur])
continue;
for (pair<int, int> i : g[cur])
if (res[i.first] > cost + i.second) {
res[i.first] = cost + i.second;
rf[i.first] = {cur, i.second};
nxt.push({-res[i.first], i.first});
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
for (int i = 0; i < M; i++) {
g[R[i][0]].push_back({R[i][1], L[i]});
g[R[i][1]].push_back({R[i][0], L[i]});
}
dijkstra(0);
char exit[N];
memset(exit, 0, sizeof exit);
for (int i = 0; i < K; i++)
exit[P[i]] = 1;
char rem[N];
memset(rem, 0, sizeof rem);
for (bool again = 1; again;) {
again = 0;
dijkstra(0);
int opt = -1;
for (int i = 0; i < N; i++)
if (exit[i] && (opt == -1 || res[opt] > res[i]))
opt = i;
//cout << res[opt] << " " << opt << endl;
while (rf[opt].first != -1) {
int prev = rf[opt].first;
//cout << prev << endl;
if (!rem[prev]) {
again = 1;
vector<pair<int, int>> nxtVec;
bool erased = 0;
for (auto i : g[prev])
if (!erased && i.first == opt && i.second == rf[opt].second)
erased = 1;
else
nxtVec.push_back(i);
assert(erased);
rem[prev] = 1;
g[prev] = nxtVec;
}
opt = prev;
}
}
dijkstra(0);
int ans = inf;
for (int i = 0; i < N; i++)
if (exit[i] && (ans > res[i]))
ans = res[i];
return ans;
}
//31 11
//g++ -std=c++14 grader.cpp crocodile.cpp
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
