Submission #1090738

#TimeUsernameProblemLanguageResultExecution timeMemory
1090738_callmelucianCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
255 ms29272 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pl; typedef pair<int,int> pii; typedef tuple<int,int,int> tt; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) const int mn = 1e5 + 5; vector<pl> adj[mn]; bool vis[mn]; void dijkstra (int source, vector<ll> &dist, int n) { for (int i = 1; i <= n; i++) vis[i] = 0, dist[i] = LLONG_MAX; dist[source] = 0; priority_queue<pl> pq; pq.emplace(0, source); while (pq.size()) { int a = pq.top().second; pq.pop(); if (vis[a]) continue; vis[a] = 1; for (pl it : adj[a]) { int b; ll w; tie(b, w) = it; if (dist[a] + w < dist[b]) { dist[b] = dist[a] + w; pq.emplace(-dist[b], b); } } } return; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; int S, T, U, V; cin >> S >> T >> U >> V; vector<tt> edge(m); for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; edge[i] = {a, b, c}; adj[a].emplace_back(b, c); adj[b].emplace_back(a, c); } vector<ll> distS(n + 1), distT(n + 1), distU(n + 1), distV(n + 1), dist(n + 1); dijkstra(S, distS, n); dijkstra(T, distT, n); dijkstra(U, distU, n); dijkstra(V, distV, n); ll ans = LLONG_MAX; // S -> T direction for (int i = 1; i <= n; i++) adj[i].clear(); for (int i = 1; i <= n; i++) { if (distU[i] != LLONG_MAX) adj[U].emplace_back(i, distU[i]); if (distV[i] != LLONG_MAX) adj[i].emplace_back(V, distV[i]); } for (int i = 0; i < m; i++) { int a, b, c; tie(a, b, c) = edge[i]; if (max(distS[a], distT[b]) != LLONG_MAX) if (distS[a] + c + distT[b] == distS[T]) adj[a].emplace_back(b, 0); if (max(distS[b], distT[a]) != LLONG_MAX) if (distS[b] + c + distT[a] == distS[T]) adj[b].emplace_back(a, 0); } dijkstra(U, dist, n); ans = min(ans, dist[V]); // T -> S direction for (int i = 1; i <= n; i++) adj[i].clear(); for (int i = 1; i <= n; i++) { if (distU[i] != LLONG_MAX) adj[U].emplace_back(i, distU[i]); if (distV[i] != LLONG_MAX) adj[i].emplace_back(V, distV[i]); } for (int i = 0; i < m; i++) { int a, b, c; tie(a, b, c) = edge[i]; if (max(distT[a], distS[b]) != LLONG_MAX) if (distT[a] + c + distS[b] == distT[S]) adj[a].emplace_back(b, 0); if (max(distT[b], distS[a]) != LLONG_MAX) if (distT[b] + c + distS[a] == distT[S]) adj[b].emplace_back(a, 0); } dijkstra(U, dist, n); ans = min(ans, dist[V]); cout << ans; 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...