#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int> > > adjlist;
vector<vector<pair<int,int> > > treeadjlist;
int INF = 100000000;
vector<bool> isEnd;
vector<bool> visited;
vector<pair<int,int> > predecessor;
vector<int> distances;
int dfs(int x){
//cout<<x<<endl;
visited[x]=true;
int min1 = INF;
int min2 = INF;
if (isEnd[x]){
visited[x]=false;
return 0;
}
for (auto p : treeadjlist[x]){
if (visited[p.second]){
continue;
}
int distance = p.first+dfs(p.second);
if (distance<min1){
min2=min1;
min1=distance;
} else if (distance<min2){
min2=distance;
}
}
visited[x]=false;
return min2;
}
int origdfs(int x){
//cout<<x<<endl;
visited[x]=true;
int min1 = INF;
int min2 = INF;
if (isEnd[x]){
visited[x]=false;
return 0;
}
for (auto p : adjlist[x]){
if (visited[p.second]){
continue;
}
int distance = p.first+origdfs(p.second);
if (distance<min1){
min2=min1;
min1=distance;
} else if (distance<min2){
min2=distance;
}
}
visited[x]=false;
return min2;
}
void dijkstra(int start){
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
pq.push(make_pair(start,0));
distances[start]=0;
while (pq.size()>0){
auto f = pq.top();
pq.pop();
if (distances[f.second]<f.first){
continue;
}
if (predecessor[f.second].first!=-1){
treeadjlist[predecessor[f.second].second].push_back(make_pair(predecessor[f.second].first,f.second));
}
for (auto i : adjlist[f.second]){
if (distances[i.second]>distances[f.second]+i.first){
distances[i.second]=distances[f.second]+i.first;
pq.push(make_pair(distances[i.second],i.second));
predecessor[i.second]=make_pair(i.first,f.second);
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
adjlist.resize(N);
treeadjlist.resize(N);
for (int i = 0; i<M; i++){
adjlist[R[i][0]].push_back(make_pair(L[i],R[i][1]));
adjlist[R[i][1]].push_back(make_pair(L[i],R[i][0]));
}
isEnd.resize(N,false);
visited.resize(N,false);
distances.resize(N,INF);
predecessor.resize(N,make_pair(-1,-1));
for (int i = 0; i<K; i++){
isEnd[P[i]]=true;
}
dijkstra(0);
int d = dfs(0);
if (d!=INF){
return d;
} else {
visited.resize(N,false);
return origdfs(0);
}
}
#include "crocodile.h"
#include <stdio.h>
#include <stdlib.h>
#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;
}
Compilation message
/tmp/cc6uPWnY.o: In function `read_input()':
grader.cpp:(.text+0x0): multiple definition of `read_input()'
/tmp/ccPMxy9X.o:crocodile.cpp:(.text+0x240): first defined here
/tmp/cc6uPWnY.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccPMxy9X.o:crocodile.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
