Submission #357645

#TimeUsernameProblemLanguageResultExecution timeMemory
357645cute_haterCommuter Pass (JOI18_commuter_pass)C++17
31 / 100
379 ms24248 KiB
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <algorithm> #include <string> #include <cmath> #include <cstdio> #include <iomanip> #include <fstream> #include <cassert> #include <cstring> #include <numeric> #include <ctime> #include <complex> #include <bitset> #include <random> #include <climits> #include <stack> /*#pragma GCC optimize("Ofast") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")*/ using namespace std; typedef long long ll; typedef long double ld; #define int ll #define double ld #define loop(i, n) for(int i = 0; i < (int)n; ++i) #define loop1(i, n) for(int i = 1; i <= (int)n; ++i) #define F first #define S second #define pb push_back #define pi pair <int, int> #define all(x) begin(x), end(x) #define ti tuple <int, int, int> #define Point Vect #define no {cout << -1; return;} #define yes {cout << "Yes"; return;} #define mkp make_pair #define mkt make_tuple #define cerr if(0) cerr const int N = 1e5 + 7, INF = 1e18, SN = 305; vector <pi> g[N]; int dist[4][N], all_dist[SN][SN]; ti ed[2 * N]; bool good[N], used[N]; void dijkstra(int fst, int f) { priority_queue <pi, vector <pi>, greater <pi> > q; q.push({ 0, fst }); loop(i, N) dist[f][i] = INF; dist[f][fst] = 0; while (!q.empty()) { int v = q.top().S, dv = q.top().F; q.pop(); if (dv > dist[f][v]) continue; for (pi u : g[v]) if (dist[f][u.F] > dist[f][v] + u.S) { dist[f][u.F] = dist[f][v] + u.S; q.push({ dist[f][u.F], u.F }); } } } void floyd(int n) { loop1(i, n) loop1(j, n) all_dist[i][j] = (i == j ? 0 : INF); loop1(i, n) for (pi j : g[i]) all_dist[i][j.F] = j.S; loop1(w, n) loop1(u, n) loop1(v, n) all_dist[u][v] = min(all_dist[u][v], all_dist[u][w] + all_dist[w][v]); } void solve() { int n, m, s, t, a, b; cin >> n >> m >> s >> t >> a >> b; loop(i, m) { int u, v, c; cin >> u >> v >> c; g[u].pb({ v, c }); g[v].pb({ u, c }); ed[i] = mkt(u, v, c); } dijkstra(s, 0); dijkstra(t, 1); dijkstra(a, 2); dijkstra(b, 3); int len = dist[0][t]; loop(i, m) { int u, v, c; tie(u, v, c) = ed[i]; if (dist[0][u] + c + dist[1][v] == len || dist[0][v] + c + dist[1][u] == len) good[u] = good[v] = 1; } int ans = dist[3][a]; if (n <= 300) { floyd(n); loop1(i, n) loop1(j, n) if (good[i] && good[j] && all_dist[i][j] == len - min(dist[2][i] + dist[3][j], dist[2][j] + dist[3][i])) ans = min({ ans, dist[2][i] + dist[3][j], dist[2][j] + dist[3][i] }); } else if (s == a) { loop1(i, n) if (good[i]) ans = min(ans, dist[3][i]); } else { int cla = s, clb = s; loop1(i, n) if (good[i]) { if (dist[2][cla] > dist[2][i]) cla = i; if (dist[3][clb] > dist[3][i]) clb = i; } ans = min(ans, dist[2][cla] + dist[3][clb]); } cout << ans; } signed main() { //freopen("b2.txt", "r", stdin); //freopen("ans9.txt", "w", stdout); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //int t; cin >> t; loop(i, t) solve(); 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...