제출 #525390

#제출 시각아이디문제언어결과실행 시간메모리
525390na2aCommuter Pass (JOI18_commuter_pass)C++14
16 / 100
681 ms64912 KiB
#include <iostream> #include <iomanip> #include <cstdlib> #include <algorithm> #include <fstream> #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <ctime> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <deque> #include <cassert> #include <unordered_map> #include <bitset> #include <unordered_set> using namespace std; #define pb push_back #define pp pop_back #define f first #define s second #define mp make_pair const int N = (int) 1e6 + 123; int n, m; int S, T, U, V; int edgeFrom[N]; int edgeTo[N]; int edgeWeight[N]; vector<int> g[N]; vector<int> dag[N]; long long d[4][N]; void dijkstra(long long *dist, int start) { for (int i = 1; i <= n; i++) dist[i] = (long long) 1e18; dist[start] = 0; set<pair<long long, int>> s; s.insert(make_pair(0, start)); while (!s.empty()) { int v = s.begin() -> second; s.erase(s.begin()); for (int edge : g[v]) { int to = ((edgeFrom[edge] ^ edgeTo[edge]) ^ v); if (dist[to] > dist[v] + edgeWeight[edge]) { s.erase(make_pair(dist[to], to)); dist[to] = dist[v] + edgeWeight[edge]; s.insert(make_pair(dist[to], to)); } } } } bool used[N]; long long minU[N]; long long minV[N]; long long ans = 1e18; void dfs(int v) { if (used[v]) return; used[v] = true; minU[v] = d[2][v]; minV[v] = d[3][v]; for (auto to : dag[v]) { dfs(to); minU[v] = min(minU[v], minU[to]); minV[v] = min(minV[v], minV[to]); } ans = min(ans, d[2][v] + minV[v]); ans = min(ans, d[3][v] + minU[v]); } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; cin >> S >> T; cin >> U >> V; for (int i = 1; i <= m; i++) { cin >> edgeFrom[i] >> edgeTo[i] >> edgeWeight[i]; g[edgeFrom[i]].push_back(i); g[edgeTo[i]].push_back(i); } dijkstra(d[0], S); dijkstra(d[1], T); dijkstra(d[2], U); dijkstra(d[3], V); long long shortest = d[0][T]; for (int i = 1; i <= m; i++) { if (d[0][edgeFrom[i]] + edgeWeight[i] + d[1][edgeTo[i]] == shortest) { dag[edgeFrom[i]].push_back(edgeTo[i]); dag[edgeTo[i]].push_back(edgeFrom[i]); } else if (d[0][edgeTo[i]] + edgeWeight[i] + d[1][edgeFrom[i]] == shortest) { dag[edgeTo[i]].push_back(edgeFrom[i]); dag[edgeFrom[i]].push_back(edgeTo[i]); } } dfs(S); 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...