#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
typedef long long ll;
typedef pair<ll, int> pii;
const int MAXN = 1e5 + 10;
const ll inf = 1e18;
int n, m, k, ext[MAXN];
ll g[MAXN], f[MAXN];
vector<pair<int, int> > adj[MAXN];
priority_queue<pii, vector<pii>, greater<pii> > q;
void dijkstra(){
for(int i = 1; i <= n; i++)
g[i] = f[i] = inf;
for(int i = 1; i <= k; i++){
int u = ext[i];
g[u] = f[u] = 0; q.push(mp(0, u));
}
while(!q.empty()){
pii p = q.top(); q.pop();
int u = p.se;
if(p.fi != f[u]) continue;
for(int i = 0; i < (int)adj[u].size(); i++){
int v = adj[u][i].fi, w = adj[u][i].se;
if(f[u] + w < g[v]){
if(chkmin(f[v], g[v]) && f[v] != inf)
q.push(mp(f[v], v));
g[v] = f[u] + w;
}else if(chkmin(f[v], f[u] + w))
q.push(mp(f[v], v));
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
// input
n = N, m = M, k = K;
for(int i = 0; i < m; i++){
int a = R[i][0] + 1, b = R[i][1] + 1, c = L[i];
adj[a].pb(mp(b, c));
adj[b].pb(mp(a, c));
}
for(int i = 1; i <= k; i++)
ext[i] = P[i - 1] + 1;
// dijkstra
dijkstra();
return (int)f[1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 9 |
Correct |
3 ms |
2916 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2656 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 12 |
Correct |
5 ms |
3148 KB |
Output is correct |
| 13 |
Correct |
4 ms |
3148 KB |
Output is correct |
| 14 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 9 |
Correct |
3 ms |
2916 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2656 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 12 |
Correct |
5 ms |
3148 KB |
Output is correct |
| 13 |
Correct |
4 ms |
3148 KB |
Output is correct |
| 14 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 16 |
Correct |
366 ms |
48572 KB |
Output is correct |
| 17 |
Correct |
64 ms |
14500 KB |
Output is correct |
| 18 |
Correct |
91 ms |
15952 KB |
Output is correct |
| 19 |
Correct |
455 ms |
53620 KB |
Output is correct |
| 20 |
Correct |
281 ms |
42720 KB |
Output is correct |
| 21 |
Correct |
32 ms |
7904 KB |
Output is correct |
| 22 |
Correct |
272 ms |
38060 KB |
Output is correct |
