#include <bits/stdc++.h>
#include "crocodile.h"
#include <cassert>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
int n, m, k, dist[NMAX][2], R[NMAX * 10][2], L[NMAX * 10], P[NMAX], v[NMAX], a, b;
vector<pair<int, int>> adj[NMAX];
int travel_plan(int N_, int M_, int R_[][2], int L[], int K_, int P_[]){
n = N_; m = M_; k = K_;
for(int i = 0; i < m; i++){
a = R[i][0]; b = R[i][1];
adj[a].emplace_back(b, L[i]);
adj[b].emplace_back(a, L[i]);
//cout << a << ' ' << b << ' ' << L[i] << '\n';
}
memset(dist, 0x3f, sizeof(dist));
priority_queue<pair<int, int>> pq;
for(int i = 0; i < k; i++) {
dist[P_[i]][0] = dist[P_[i]][1] = 0;
pq.emplace(0, P_[i]);
v[P_[i]] = 1;
}
while(pq.size()){
auto[d, x] = pq.top(); pq.pop();
//cout << x << ' ' << d << '\n';
d = -d;
if(++v[x] != 2) continue;
for(auto&[nx, p] : adj[x]){
ll nxd = d + p;
//cout << "nxd is " << nx << ' ' << nxd << '\n';
if(nxd < dist[nx][1]){
pq.emplace(-nxd, nx);
dist[nx][1] = nxd;
if(dist[nx][0] > dist[nx][1]) swap(dist[nx][0], dist[nx][1]);
}
}
}
assert(dist[0][1] <= 1e9);
return dist[0][1];
}
/*
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
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];
int ans;
cin >> ans;
cout << travel_plan(n, m, R, L, k, P);
cout << ' ' << ans << '\n';
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
6740 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
6740 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
6740 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
