This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <algorithm>
#define INF 0x7fffffff
using namespace std;
pair <int,int> Road[10000001];
pair <int,int> Heap[5000001];
int V, E, Q, D[500001], Check[500001], Size, Next[10000001], Loc[500001], Start[500001];
void input(void) {
int i, v1, v2, q;
scanf("%d %d %d",&V,&E,&Q);
for(i=1 ; i<=E ; i++) {
scanf("%d %d %d",&v1,&v2,&q);
if(!Start[v1])
Start[v1]=2*i-1;
Next[Loc[v1]]=2*i-1;
Loc[v1]=2*i-1;
Road[2*i-1]=make_pair(v2,q);
if(!Start[v2])
Start[v2]=2*i;
Next[Loc[v2]]=2*i;
Loc[v2]=2*i;
Road[2*i]=make_pair(v1,q);
}
}
void process(void) {
int i, Now, Value;
for(i=2 ; i<=V ; i++)
D[i]=-1;
D[1]=INF;
Size=1;
Heap[0]=make_pair(D[1],1);
while(Size) {
Now=Heap[0].second;
pop_heap(Heap,Heap+Size);
Size--;
if(Check[Now])
continue;
Check[Now]=1;
i=Start[Now];
while(i) {
Value=min(D[Now],Road[i].second);
if(D[Road[i].first]<Value) {
D[Road[i].first]=Value;
Heap[Size++]=make_pair(Value,Road[i].first);
push_heap(Heap,Heap+Size);
}
i=Next[i];
}
}
}
void output(void) {
int i, X;
for(i=1 ; i<=Q ; i++) {
scanf("%d",&X);
printf("%d\n",D[X]);
}
}
int main(void) {
input();
process();
output();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |