Submission #1226620

#TimeUsernameProblemLanguageResultExecution timeMemory
1226620wedonttalkanymoreCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
226 ms23928 KiB
#include <bits/stdc++.h> #define pii pair <long long, long long> #define fi first #define se second using namespace std; using ll = long long; const ll N = 100005, inf = 1e16; int n, m, S, T, U, V; vector <pii> adj[N]; ll dist_s[N], dist_t[N], dist_ans[N][3]; int a[N], b[N], c[N]; void dijkstra(int x, ll *length) { for (int i = 1; i <= n; i++) length[i] = inf; length[x] = 0; priority_queue <pii, vector <pii>, greater <pii> > q; q.push({length[x], x}); while(q.size()) { auto tmp = q.top(); q.pop(); ll u = tmp.se, z = tmp.fi; if (z > length[u]) continue; for (auto v : adj[u]) { if (length[v.fi] > length[u] + v.se) { length[v.fi] = length[u] + v.se; q.push({length[v.fi], v.fi}); } } } } struct item { ll val, x, pre; bool operator <(const item &other) const { return val > other.val; } }; struct node { ll u, w, type; }; vector <node> adj1[N], adj2[N]; void dijkstra1(int root, vector <node> adj_x[]) { for (int i = 1; i <= n; i++) for (int j = 0; j < 3; j++) dist_ans[i][j] = inf; dist_ans[root][0] = 0; priority_queue <item> q; q.push({dist_ans[root][0], root, 0}); while(q.size()) { auto tmp = q.top(); q.pop(); ll val = tmp.val, u = tmp.x, pre = tmp.pre; if (val > dist_ans[u][pre]) continue; for (auto v : adj_x[u]) { int x = min(u, v.u), y = max(u, v.u); if (pre == 0) { if (dist_ans[v.u][0] > dist_ans[u][pre] + v.w) { // tiep tuc ko dung ve va di tiep dist_ans[v.u][0] = dist_ans[u][pre] + v.w; q.push({dist_ans[v.u][0], v.u, 0}); } if (v.type == 0 && dist_ans[v.u][1] > dist_ans[u][pre]) { // bat dau dung ve dist_ans[v.u][1] = dist_ans[u][pre]; q.push({dist_ans[v.u][1], v.u, 1}); } } else if (pre == 1) { if (v.type == 0 && dist_ans[v.u][1] > dist_ans[u][pre]) { dist_ans[v.u][1] = dist_ans[u][pre]; q.push({dist_ans[v.u][1], v.u, 1}); } if (dist_ans[v.u][2] > dist_ans[u][pre] + v.w) { // ko dung ve nua dist_ans[v.u][2] = dist_ans[u][pre] + v.w; q.push({dist_ans[v.u][2], v.u, 2}); } } else if (pre == 2) { if (dist_ans[v.u][2] > dist_ans[u][pre] + v.w) { dist_ans[v.u][2] = dist_ans[u][pre] + v.w; q.push({dist_ans[v.u][2], v.u, 2}); } } } } } signed main() { cin >> n >> m; cin >> S >> T; cin >> U >> V; for (int i = 1; i <= m; i++) { cin >> a[i] >> b[i] >> c[i]; adj[a[i]].emplace_back(b[i], c[i]); adj[b[i]].emplace_back(a[i], c[i]); } dijkstra(S, dist_s); dijkstra(T, dist_t); // for (int i = 1; i <= n; i++) cout << dist_s[i] << ' ' << dist_t[i] << '\n'; ll minn = dist_s[T]; // khoang cach ngan nhat tu s den t for (int i = 1; i <= m; i++) { int u = a[i], v = b[i]; bool free_uv = (dist_s[u] + c[i] + dist_t[v] == minn); bool free_vu = (dist_s[v] + c[i] + dist_t[u] == minn); adj1[u].push_back({v, c[i], free_uv ? 0 : -1}); adj1[v].push_back({u, c[i], free_vu ? 0 : -1}); adj2[u].push_back({v, c[i], free_vu ? 0 : -1}); adj2[v].push_back({u, c[i], free_uv ? 0 : -1}); } dijkstra1(U, adj1); int x = min({dist_ans[V][0], dist_ans[V][1], dist_ans[V][2]}); // cout << dist_ans[V][0] << ' ' << dist_ans[V][1] << ' ' << dist_ans[V][2] << '\n'; dijkstra1(U, adj2); int y = min({dist_ans[V][0], dist_ans[V][1], dist_ans[V][2]}); // cout << dist_ans[V][0] << ' ' << dist_ans[V][1] << ' ' << dist_ans[V][2] << '\n'; cout << min(x, y); 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...