Submission #81466

#TimeUsernameProblemLanguageResultExecution timeMemory
81466igziCities (BOI16_cities)C++17
14 / 100
696 ms33516 KiB
#include <bits/stdc++.h> #define maxN 100002 using namespace std; vector < pair<long long,long long> > adj[maxN]; vector <long long> v,u; long long n,m,k,i,x,y,z,d[7][maxN]; pair <long long,long long> par[7][maxN]; void dijkstra(int n,int x){ priority_queue < pair<long long,long long>, vector< pair<long long,long long> > , greater< pair<long long,long long> > > pq; bool mar[maxN]; pq.push(make_pair(0,n)); for(int i=0;i<maxN;i++){ mar[i]=false; d[x][i]=LLONG_MAX; } d[x][n]=0; par[x][n]=make_pair(-1,-1); while(!pq.empty()){ long long c=pq.top().second; pq.pop(); if(mar[c]) continue; mar[c]=true; for(int i=0;i<adj[c].size();i++){ if(d[x][adj[c][i].first]>d[x][c]+adj[c][i].second){ d[x][adj[c][i].first]=d[x][c]+adj[c][i].second; par[x][adj[c][i].first]=make_pair(c,i); pq.push(make_pair(d[x][adj[c][i].first],adj[c][i].first)); } } } } int main() { long long t=LLONG_MAX; cin>>n>>k>>m; for(i=0;i<k;i++){ cin>>x; v.push_back(x); } for(i=0;i<m;i++){ cin>>x>>y>>z; adj[x].push_back(make_pair(y,z)); adj[y].push_back(make_pair(x,z)); } for(i=0;i<k;i++) dijkstra(v[i],i); if(k==2) {cout<<d[0][v[1]]<<endl; return 0;} for(i=0;i<n;i++) t=min(t,d[0][i]+d[1][i]+d[2][i]); cout<<t<<endl; return 0; }

Compilation message (stderr)

cities.cpp: In function 'void dijkstra(int, int)':
cities.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[c].size();i++){
                 ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...