Submission #528505

#TimeUsernameProblemLanguageResultExecution timeMemory
528505georgerapeanuCommuter Pass (JOI18_commuter_pass)C++11
0 / 100
397 ms32000 KiB
#include <bits/stdc++.h> using namespace std; const long long inf = 1e18; vector<long long> dijkstra(int source, const vector<vector<pair<int, long long> > > &graph){ vector<long long> dist(graph.size(), inf); dist[source] = 0; priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > pq; pq.push({dist[source], source}); while(!pq.empty()){ int nod = pq.top().second; long long cost = pq.top().first; pq.pop(); if(cost != dist[nod]){ continue; } for(auto it:graph[nod]){ if(dist[it.first] > dist[nod] + it.second){ dist[it.first] = dist[nod] + it.second; pq.push({dist[it.first], it.first}); } } } return dist; } long long best_distance(const vector<long long> &dist_u, const vector<long long> &dist_v, vector<vector<pair<int, long long> > > &graph, const vector<pair<int,int> > &edges, int n){ for(auto it:dist_u)printf("%lld ", it);printf("\n"); for(auto it:dist_v)printf("%lld ", it);printf("\n"); for(int i = 0;i < n;i++){ graph[i].clear(); } for(auto it:edges){ graph[it.first].push_back({it.second, dist_v[it.second] - dist_v[it.first]}); // printf("edge from %d to %d with cost %lld\n", it.first, it.second, dist_v[it.second] - dist_v[it.first]); } if((int)graph.size() < n + 1){ graph.push_back(vector<pair<int, long long> >()); }else{ graph[n].clear(); } for(int i = 0;i < n;i++){ graph[n].push_back({i, dist_u[i] + dist_v[i]}); // printf("edge from %d to %d with cost %lld\n", n, i, dist_u[i] + dist_v[i]); } //printf("\n"); vector<long long> dist = dijkstra(n, graph); long long best_dist = inf; for(int i = 0;i < n;i++){ best_dist = min(best_dist, dist[i]); } return best_dist; } int main(){ int n, m; int s, t; int u, v; scanf("%d %d", &n, &m); scanf("%d %d", &s, &t); scanf("%d %d", &u, &v); s--; v--; t--; u--; vector<vector<pair<int, long long> > > graph(n, vector<pair<int, long long> >()); vector<pair<pair<int, int>,int> > edges; for(int i = 1;i <= m;i++){ int a, b, c; scanf("%d %d %d", &a, &b, &c); a--; b--; graph[a].push_back({b, c}); graph[b].push_back({a, c}); edges.push_back({{a, b}, c}); } vector<long long> dist_s = dijkstra(s, graph); vector<long long> dist_t = dijkstra(t, graph); vector<long long> dist_u = dijkstra(u, graph); vector<long long> dist_v = dijkstra(v, graph); vector<pair<int, int> > new_edges; for(auto it:edges){ if(dist_t[it.first.first] + dist_s[it.first.second] + it.second == dist_s[t]){ new_edges.push_back({it.first.second, it.first.first}); } if(dist_s[it.first.first] + dist_t[it.first.second] + it.second == dist_s[t]){ new_edges.push_back({it.first.first, it.first.second}); } } long long fst = best_distance(dist_u, dist_v, graph, new_edges, n); long long snd = best_distance(dist_v, dist_u, graph, new_edges, n); long long trd = dist_u[v]; printf("%lld\n", min(min(fst, snd), trd)); return 0; }

Compilation message (stderr)

commuter_pass.cpp: In function 'long long int best_distance(const std::vector<long long int>&, const std::vector<long long int>&, std::vector<std::vector<std::pair<int, long long int> > >&, const std::vector<std::pair<int, int> >&, int)':
commuter_pass.cpp:33:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   33 |   for(auto it:dist_u)printf("%lld ", it);printf("\n");
      |   ^~~
commuter_pass.cpp:33:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   33 |   for(auto it:dist_u)printf("%lld ", it);printf("\n");
      |                                          ^~~~~~
commuter_pass.cpp:34:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   34 |   for(auto it:dist_v)printf("%lld ", it);printf("\n");
      |   ^~~
commuter_pass.cpp:34:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   34 |   for(auto it:dist_v)printf("%lld ", it);printf("\n");
      |                                          ^~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%d %d", &s, &t);
      |   ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     scanf("%d %d %d", &a, &b, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...