Submission #8129

#TimeUsernameProblemLanguageResultExecution timeMemory
8129baneling100Sightseeing (NOI14_sightseeing)C++98
15 / 25
3500 ms139584 KiB
#include <stdio.h> #include <algorithm> #include <vector> #include <queue> #define INF 0x7fffffff using namespace std; typedef pair <int,int> ppair; vector <ppair> A[500001]; pair <int,int> Heap[5000001]; int V, E, Q, D[500001], Check[500001], Size; 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); A[v1].push_back(make_pair(v2,q)); A[v2].push_back(make_pair(v1,q)); } } void process(void) { int i, j, 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; j=A[Now].size(); for(i=0 ; i<j ; i++) { Value=min(D[Now],A[Now][i].second); if(D[A[Now][i].first]<Value) { D[A[Now][i].first]=Value; Heap[Size++]=make_pair(Value,A[Now][i].first); push_heap(Heap,Heap+Size); } } } } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...