Submission #8128

#TimeUsernameProblemLanguageResultExecution timeMemory
8128baneling100Sightseeing (NOI14_sightseeing)C++98
15 / 25
3500 ms165568 KiB
#include <stdio.h> #include <algorithm> #include <vector> #include <queue> #define INF 0x7fffffff using namespace std; typedef pair <int,int> ppair; priority_queue <ppair> MaxQ; vector <ppair> A[500001]; int V, E, Q, X[500000], D[500001], Check[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); A[v1].push_back(make_pair(v2,q)); A[v2].push_back(make_pair(v1,q)); } for(i=1 ; i<=Q ; i++) scanf("%d",&X[i]); } void process(void) { int i, j, Now, Value; for(i=2 ; i<=V ; i++) D[i]=-1; D[1]=INF; MaxQ.push(make_pair(D[1],1)); while(!MaxQ.empty()) { Now=MaxQ.top().second; MaxQ.pop(); 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; MaxQ.push(make_pair(Value,A[Now][i].first)); } } } } void output(void) { int i; for(i=1 ; i<=Q ; i++) printf("%d\n",D[X[i]]); } 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...