//#include "crocodile.h"
#include <bits/stdc++.h>
#define INF 1e18
#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;
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
#define pb push_back
vector<vector<pair<ll,ll>>> G;
ll dist[10001];
vi parent(10001, 0);
ll best[10010];
void dijkstra(ll n){
dist[n]=0;
priority_queue<ii,vector<ii>,greater<ii> > pq;
pq.push(ii(0,n));
while(!pq.empty()){
ii front=pq.top();
pq.pop();
ll u=front.second,d=front.first;
if(d>dist[u])continue;
for(int i=0;i<G[u].size();i++){
ii v=G[u][i];
if(dist[u]+v.second<dist[v.first]){
dist[v.first]=dist[u]+v.second;
parent[v.first]=u;
pq.push(ii(dist[v.first],v.first));
}
}
}
}
ll res;
int vis[10010];
int swich[10010];
void dfs(ll x,ll pos){
vis[x]=1;
if(swich[x]==1){
res=min(res,pos);
return;
}
vector<pair<pair<ll,ll>,ll>> gg;
for(int i=0;i<G[x].size();i++){
gg.pb(make_pair(ii(best[G[x][i].first],G[x][i].second),G[x][i].first));
}
int sw=0;
sort(gg.begin(),gg.end());
for(int i=0;i<gg.size();i++){
if(vis[gg[1].second]==-1){
if(sw==1){
dfs(gg[i].second,pos+gg[i].first.second);
break;
}
else{
sw=1;
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
memset(swich,-1,sizeof swich);
for(int i=0;i<K;i++){
swich[P[i]]=1;
}
res=INF;
memset(vis,-1,sizeof vis);
G.assign(N,vector<pair<ll,ll>>());
for(int i=0;i<M;i++){
G[R[i][0]].pb(make_pair(R[i][1],L[i]));
G[R[i][1]].pb(make_pair(R[i][0],L[i]));
}
for(int i=0;i<N;i++){
memset(dist,INF,sizeof dist);
dijkstra(i);
ll curr=INF;
for(int j=0;j<K;j++){
curr=min(curr,dist[P[i]]);
}
best[i]=curr;
}
dfs(0,0);
return res;
}
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;
}
Compilation message
crocodile.cpp: In function 'void dijkstra(ll)':
crocodile.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<G[u].size();i++){
~^~~~~~~~~~~~
crocodile.cpp: In function 'void dfs(ll, ll)':
crocodile.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<G[x].size();i++){
~^~~~~~~~~~~~
crocodile.cpp:57:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<gg.size();i++){
~^~~~~~~~~~
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:83:32: warning: overflow in implicit constant conversion [-Woverflow]
memset(dist,INF,sizeof dist);
^
/tmp/ccmxALgc.o: In function `read_input()':
grader.cpp:(.text+0x0): multiple definition of `read_input()'
/tmp/ccO0VLtE.o:crocodile.cpp:(.text+0x70): first defined here
/tmp/ccmxALgc.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccO0VLtE.o:crocodile.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
