제출 #977399

#제출 시각아이디문제언어결과실행 시간메모리
9773990x34cCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
494 ms56464 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> #define piii pair<int, pii> #define endl '\n' #define int ll using namespace std; const int INF = 1e9*2e6 + 100; struct node { int v, w, dw, x; }; class Compare { public: bool operator()(node &a, node &b) { if(a.w == b.w) return a.dw > b.dw; return a.w > b.w; } }; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int N, M; cin >> N >> M; int S, T, U, V; cin >> S >> T >> U >> V; --S; --T; --U; --V; vector<vector<pii>> graph(N); for(int i = 0; i < M; i++) { int a, b, c; cin >> a >> b >> c; --a; --b; graph[a].push_back({b, c}); graph[b].push_back({a, c}); } auto dijkstra = [graph](int S, vector<int> &dist) { priority_queue<pii, vector<pii>, greater<pii>> pq; pq.push({0, S}); dist[S] = 0; while(!pq.empty()) { int w, v; tie(w, v) = pq.top(); pq.pop(); for(pii u : graph[v]) { if(dist[u.first] > w + u.second) { dist[u.first] = w + u.second; pq.push({dist[u.first], u.first}); } } } }; vector<int> distV(N, INF), distU(N, INF); dijkstra(V, distV); dijkstra(U, distU); vector<vector<pii>> dist(N, vector<pii>(1LL << 2, {INF, INF})); dist[S][0] = {0, 0}; priority_queue<node, vector<node>, Compare> pq; pq.push({S, 0, 0, 0}); while(!pq.empty()) { int v = pq.top().v, w = pq.top().w, dw = pq.top().dw, x = pq.top().x; pq.pop(); // go to state 1 if(!(x & 1) && (dist[v][x | 1].first > w || (dist[v][x | 1].first == w && dist[v][x | 1].second > dw + distU[v]))) { dist[v][x | 1] = {w, dw + distU[v]}; pq.push({v, w, dw + distU[v], x|1}); } // go to state 2 if(!(x & 2) && (dist[v][x | 2].first > w || (dist[v][x | 2].first == w && dist[v][x | 2].second > dw + distV[v]))) { dist[v][x | 2] = {w, dw + distV[v]}; pq.push({v, w, dw + distV[v], x|2}); } for(pii u : graph[v]) { if((dist[u.first][x].first > w + u.second) || (dist[u.first][x].first == w + u.second && dist[u.first][x].second > dw)) { dist[u.first][x] = {w + u.second, dw}; pq.push({u.first, w + u.second, dw, x}); } } } cout << min(distV[U], dist[T][3].second) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...