Submission #934379

#TimeUsernameProblemLanguageResultExecution timeMemory
934379SmuggingSpunCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
179 ms21836 KiB
#include<bits/stdc++.h> #define taskname "commuterpass" using namespace std; typedef long long ll; template<class T>void minimize(T& a, T b){ if(a > b){ a = b; } } const ll INF = 1e18; const int lim = 1e5 + 5; vector<pair<int, int>>e[lim]; void dijkstra(int vertex, vector<ll>& d){ priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>pq; pq.emplace(d[vertex] = 0, vertex); bitset<lim>vis; while(!pq.empty()){ auto [w, u] = pq.top(); pq.pop(); if(w == d[u]){ for(auto& [v, edge_w] : e[u]){ ll W = w + edge_w; if(W < d[v]){ pq.emplace(d[v] = W, v); } } } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); } int n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; for(int i = 0; i < m; i++){ int a, b, c; cin >> a >> b >> c; e[a].emplace_back(b, c); e[b].emplace_back(a, c); } vector<ll>d_s(n + 1, INF), d_u(n + 1, INF), d_v(n + 1, INF), dp_u(n + 1, INF), dp_v(n + 1, INF); dijkstra(s, d_s); dijkstra(u, d_u); dijkstra(v, d_v); ll ans = d_u[v]; function<void(int)>dfs; dfs = [&] (int vertex){ if(dp_u[vertex] != INF){ return; } dp_u[vertex] = d_u[vertex]; dp_v[vertex] = d_v[vertex]; for(auto& [next_vertex, w] : e[vertex]){ if(d_s[next_vertex] + w == d_s[vertex]){ dfs(next_vertex); minimize(dp_u[vertex], dp_u[next_vertex]); minimize(dp_v[vertex], dp_v[next_vertex]); } } minimize(ans, min(dp_v[vertex] + d_u[vertex], dp_u[vertex] + d_v[vertex])); }; dfs(t); cout << ans; }

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, std::vector<long long int>&)':
commuter_pass.cpp:18:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |   auto [w, u] = pq.top();
      |        ^
commuter_pass.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |    for(auto& [v, edge_w] : e[u]){
      |              ^
commuter_pass.cpp: In lambda function:
commuter_pass.cpp:55:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |   for(auto& [next_vertex, w] : e[vertex]){
      |             ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...