Submission #522627

#TimeUsernameProblemLanguageResultExecution timeMemory
522627Andy__Andy__Sightseeing (NOI14_sightseeing)C++17
15 / 25
3549 ms177624 KiB
#include <bits/stdc++.h> #define ll long long #define int ll using namespace std; ifstream f ("test.in"); ofstream g ("test.out"); int teste=1; int n,m,q; int dp[500005]; vector < array < int ,2 > > G[500005]; set < array < int ,2 > > s; void calc() { s.insert({-(100000000),1}); while(s.size()) { auto marcel = *(s.begin()); int mnDrum= -marcel[0]; int nod = marcel[1]; s.erase(s.begin()); for(auto x:G[nod]) { int vecin = x[1]; int costDrum = -x[0]; if(min(costDrum,mnDrum) > dp[vecin]) { s.erase({-dp[vecin],vecin}); dp[vecin] = min(costDrum,mnDrum); s.insert({-dp[vecin],vecin}); } } } } void solve() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>q; for(int i=1;i<=m;++i) { int a,b,c; cin>>a>>b>>c; G[a].push_back({-c,b}); G[b].push_back({-c,a}); } for(int i=1;i<=n;++i) { dp[i] = 0; sort(G[i].begin() , G[i].end()); } calc(); for(;q--;) { int x; cin>>x; cout<<dp[x]<< '\n'; } } main() { while(teste--) { solve(); } return 0; }

Compilation message (stderr)

sightseeing.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...