제출 #1082756

#제출 시각아이디문제언어결과실행 시간메모리
1082756khoile25108Commuter Pass (JOI18_commuter_pass)C++14
15 / 100
2068 ms23288 KiB
//Created by sangph2612 #include <bits/stdc++.h> using namespace std; // #define Sang 1 #define int long long #define mp make_pair #define pb push_back #define fi first #define se second #define endl '\n' #define FOR(i, a, b) for(__typeof(b) i = a, _b = b; i <= _b; ++i) #define FORD(i, a, b) for(__typeof(a) i = a, _b = b; i >= _b; --i) #define ALL(a) (a).begin(), (a).end() #define RALL(a) (a).rbegin(), (a).rend() #define MASK(i) (1ll<<(i)) #define BIT(t, i) (((t)>>(i))&1) typedef vector<int> vi; typedef pair<int, int> ii; typedef pair<int, ii> pii; const int MOD = 1e9+7; const int N = 1e5+5; const int INF = 0x3f3f3f3f; template <class T> bool minimize(T &a, T b) { if (a > b) { a = b; return true; } return false;} template <class T> bool maximize(T &a, T b) { if (a < b) { a = b; return true; } return false;} // **** **** // * * * // * K.B * // * * // * * int n, m, s, t, u, v, dist[3][N], best[N][2], ans; // dist[i][0] : khoảng cách ngắn nhất từ s->i // dist[i][1] : khoảng cách ngắn nhất từ u->i // dist[i][2] : khoảng cách ngắn nhất từ v->i vector<ii> G[N]; void dijkstra(int st, int type){ memset(dist[type], 0x3f, sizeof dist[type]); priority_queue<ii, vector<ii>, greater<ii>> Q; dist[type][st] = 0; Q.push({dist[type][st], st}); while (!Q.empty()){ int u = Q.top().se, w = Q.top().fi; Q.pop(); if (w != dist[type][u]) continue; for (auto v : G[u]){ if (minimize(dist[type][v.fi], dist[type][u] + v.se)){ Q.push({dist[type][v.fi], v.fi}); } } } } void dfs(int u){ best[u][0] = dist[1][u]; best[u][1] = dist[2][u]; // cerr << u << endl; for (auto v : G[u]){ if (dist[0][v.fi] + v.se != dist[0][u]) continue; dfs(v.fi); minimize(best[u][0], best[v.fi][0]); minimize(best[u][1], best[v.fi][1]); } minimize(ans, dist[1][u] + best[u][1]); minimize(ans, dist[2][u] + best[u][0]); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m >> s >> t >> u >> v; FOR (i, 1, m){ int u, v, c; cin >> u >> v >> c; G[u].pb({v,c}); G[v].pb({u,c}); } dijkstra(s, 0); dijkstra(u, 1); dijkstra(v, 2); ans = dist[1][v]; dfs(t); // cout << dist[1][5] << ' ' << dist[2][2] << endl; 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...