#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
#define S second
#define F first
#define LL long long
const int N1 = 2e5+10;
const LL MOD = 1e9+7;
const LL LINF = 1e18;
const LL INF = 1e9;
vector<pair<int,int>>adj[N1];
bool vis[N1];
LL ans[N1],ans1 = LINF;
LL dfs(int i){
if(vis[i])
return ans[i];
vis[i] = 1;
LL mn1 = LINF,mn2 = LINF;
for(auto x:adj[i]){
dfs(x.F);
if(ans[x.F]+x.S<mn1)mn2 = mn1,mn1 = ans[x.F]+x.S;
else if(ans[x.F]+x.S<mn2)mn2 = ans[x.F]+x.S;
}
ans1 = min(ans1,mn2);
return ans[i] = min(ans[i],mn2);
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
int n = N;
for(int i=0;i<n;i++)
ans[i] = LINF;
for(int i=0;i<M;i++){
adj[R[i][0]].push_back({R[i][1],L[i]});
adj[R[i][1]].push_back({R[i][0],L[i]});
}
for(int i=0;i<K;i++)
vis[P[i]] = 1,ans[P[i]] = 0;
dfs(0);
return ans[0];
}
/*
#define MAX_N 50000
#define MAX_M 10000000
static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(3==scanf("%d %d %d",&N,&M,&K));
for(i=0; i<M; i++)
my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
for(i=0; i<K; i++)
my_assert(1==scanf("%d",&P[i]));
my_assert(1==scanf("%d",&solution));
}
int main()
{
int ans;
read_input();
ans = travel_plan(N,M,R,L,K,P);
if(ans==solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
return 0;
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
5068 KB |
Output is correct |
5 |
Correct |
5 ms |
5068 KB |
Output is correct |
6 |
Correct |
4 ms |
5068 KB |
Output is correct |
7 |
Correct |
4 ms |
5068 KB |
Output is correct |
8 |
Correct |
4 ms |
5068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
5068 KB |
Output is correct |
5 |
Correct |
5 ms |
5068 KB |
Output is correct |
6 |
Correct |
4 ms |
5068 KB |
Output is correct |
7 |
Correct |
4 ms |
5068 KB |
Output is correct |
8 |
Correct |
4 ms |
5068 KB |
Output is correct |
9 |
Correct |
5 ms |
5196 KB |
Output is correct |
10 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
5068 KB |
Output is correct |
5 |
Correct |
5 ms |
5068 KB |
Output is correct |
6 |
Correct |
4 ms |
5068 KB |
Output is correct |
7 |
Correct |
4 ms |
5068 KB |
Output is correct |
8 |
Correct |
4 ms |
5068 KB |
Output is correct |
9 |
Correct |
5 ms |
5196 KB |
Output is correct |
10 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |