#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+50;
vector<pair<int,ll>> g[maxn];
pair<ll,ll> cost[maxn];
int n;
bool e[maxn],vis[maxn];
void dij(){
priority_queue<pair<ll,int>> q;
for(int i=0;i<n;i++)
cost[i] = {1e18,1e18};
for(int i=0;i<n;i++)
if(e[i]){
cost[i] = {0,0};
q.push({0,i});
}
while(q.size()){
int u = q.top().second;
ll cst = -q.top().first;
q.pop();
if(vis[u])continue;
vis[u] = 1;
for(pair<int,ll> cur : g[u]){
int v = cur.first;
ll w = cur.second;
ll ncst = cst + w;
if(cost[v].second <= ncst)continue;
if(ncst < cost[v].first){
cost[v].second = cost[v].first;
cost[v].first = ncst;
}else if(ncst < cost[v].second){
cost[v].second = ncst;
}
q.push({-cost[v].second,v});
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
n = N;
for(int i=0;i<M;i++){
int u = R[i][0];
int v = R[i][1];
int w = L[i];
g[u].push_back({v,w});
g[v].push_back({u,w});
}
for(int i=0;i<K;i++)
e[P[i]] = 1;
dij();
return cost[0].second;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2680 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2808 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2680 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 9 |
Correct |
6 ms |
3064 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 12 |
Correct |
7 ms |
3448 KB |
Output is correct |
| 13 |
Correct |
7 ms |
3448 KB |
Output is correct |
| 14 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2808 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2680 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 9 |
Correct |
6 ms |
3064 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 12 |
Correct |
7 ms |
3448 KB |
Output is correct |
| 13 |
Correct |
7 ms |
3448 KB |
Output is correct |
| 14 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 16 |
Correct |
724 ms |
84704 KB |
Output is correct |
| 17 |
Correct |
111 ms |
20076 KB |
Output is correct |
| 18 |
Correct |
144 ms |
22508 KB |
Output is correct |
| 19 |
Correct |
780 ms |
93432 KB |
Output is correct |
| 20 |
Correct |
343 ms |
67704 KB |
Output is correct |
| 21 |
Correct |
52 ms |
10488 KB |
Output is correct |
| 22 |
Correct |
356 ms |
64752 KB |
Output is correct |
