#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
using int64 = long long;
const int MAXN = 1e5;
const int64 INF = 1e18L;
bitset<MAXN> is_exit, viz;
vector<pair<int,int>> G[MAXN];
int64 d1[MAXN], d2[MAXN];
int Dijkstra(int n) {
priority_queue<pair<int64,int>, vector<pair<int64,int>>, greater<pair<int64,int>>> pq;
for (int u = 0; u < n; ++u)
if (is_exit[u])
pq.emplace(0, u);
else d1[u] = d2[u] = INF;
while (!pq.empty()) {
int64 d;
int u;
tie(d, u) = pq.top();
pq.pop();
if (d != d2[u])
continue;
viz[u] = true;
for (auto it : G[u]) {
int v, w;
tie(v, w) = it;
int64 cost = d + w;
bool is_improved = false;
if (d1[v] >= cost) {
d2[v] = d1[v];
d1[v] = cost;
is_improved = true;
} else {
if (d2[v] > cost) {
d2[v] = cost;
is_improved = true;
}
}
if (is_improved || !viz[v])
pq.emplace(d2[v], v);
}
}
return d2[0];
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
for (int i = 0; i < M; ++i) {
int u = R[i][0], v = R[i][1], w = L[i];
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
for (int i = 0; i < K; ++i)
is_exit[P[i]] = true;
return Dijkstra(N);
}
/* int n, m, R[MAXN][2], L[MAXN], k, P[MAXN], sol;
void fastIO() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
int main() {
fastIO();
cin >> n >> m >> k;
for (int i = 0; i < m; ++i)
cin >> R[i][0] >> R[i][1] >> L[i];
for (int i = 0; i < k; ++i)
cin >> P[i];
cin >> sol;
int ans = travel_plan(n, m, R, L, k, P);
if (ans == sol)
cout << "OK\n";
else {
cout << "WA\n";
cout << "USER OUTPUT: " << ans << '\n';
cout << "EXPECTED ANSWER: " << sol << '\n';
}
return 0;
} */
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
