제출 #874308

#제출 시각아이디문제언어결과실행 시간메모리
874308tsumondaiCommuter Pass (JOI18_commuter_pass)C++14
15 / 100
2065 ms91008 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pb push_back #define mp make_pair #define foru(i, l, r) for(int i = l; i <= r; i++) #define ford(i, r, l) for(int i = r; i >= l; i--) #define __TIME (1.0 * clock() / CLOCKS_PER_SEC) typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 1e6 + 5; const int oo = 1e18, mod = 1e9 + 7; int n, m, k, points[5], vis[N], dpU[N], dpV[N], ans; vector<ii> adj[N]; vector<int> dag[N]; int dist[N][5]; bool mini(int &a, const int b) { if (a>b) { a=b; return true; } else { return false; } } bool maxi(int &a, const int b) { if (a<b) { a=b; return true; } else { return false; } } void dfs(int u, int par) { for (auto v: dag[u]) { if (v==par) continue; dfs(v,u); mini(dpU[u], min(dpU[v], dist[v][3])); mini(dpV[u], min(dpV[v], dist[v][4])); } mini(ans, dpU[u]+dist[u][4]); mini(ans, dpV[u]+dist[u][3]); } void dijkstra(int s) { foru(i,1,n) dist[i][s]=oo; priority_queue <pair <long long, int>> pq; pq.push(make_pair(dist[points[s]][s] = 0, points[s])); while (!pq.empty()) { //auto [du, u] = pq.top(); pq.pop(); pair<long long, long long> tmp=pq.top(); pq.pop(); long long du=tmp.first, u=tmp.second; du = -du; if (du != dist[u][s]) continue; /* for (auto [w, v]: adj[u]) if (dist[v] > du + w) { dist[v] = du + w; pq.push(make_pair(-dist[v], v)); }*/ for (pair<long long, long long> nxt: adj[u]) if (dist[nxt.second][s] > du + nxt.first) { dist[nxt.second][s] = du + nxt.first; pq.push(make_pair(-dist[nxt.second][s], nxt.second)); } } } void process() { cin >> n >> m;// 1 2 3 4 foru(i,1,4) cin >> points[i]; foru(i,1,m) { int u, v, c; cin >> u >> v >> c; adj[u].pb({c,v}); adj[v].pb({c,u}); } foru(i,1,4) dijkstra(i); foru(x,1,n) { for (auto tmp: adj[x]) { int y=tmp.se, w=tmp.fi; if (dist[x][1] + w + dist[y][2] == dist[points[2]][1]) { dag[x].pb(y); } } } ans=dist[points[3]][4]; memset(dpU, 0x3f, sizeof(dpU)); memset(dpV, 0x3f, sizeof(dpV)); dfs(points[1], 0); cout << ans; return; } signed main() { cin.tie(0)->sync_with_stdio(false); //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); process(); cerr << "Time elapsed: " << __TIME << " s.\n"; 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...