제출 #1083419

#제출 시각아이디문제언어결과실행 시간메모리
1083419icyalmondCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
343 ms63428 KiB
#include <bits/stdc++.h> #define ii pair <int, int> #define ll long long #define llll pair <ll, ll> #define ld long double #define ull unsigned long long #define el "\n" #define sp " " #define fi first #define se second #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define __lcm(a, b) (a / __gcd(a, b) * b) #define sq(x) (x) * (x) #define sqr(x) sqrtl(x) #define cbr(x) cbrtl(x) #define sz(a) (ll)(a.size()) using namespace std; const ld PI = acos(-1); const int INFI = 1e9 + 7; const ll INFL = 2e18 + 7; int n, m, s, t, u, v, x[200005], y[200005], z[200005]; vector <pair <pair <int, ll>, int>> g[100005]; ll d[5][100005]; priority_queue <pair <pair <ll, int>, int>, vector <pair <pair <ll, int>, int>>, greater <pair <pair <ll, int>, int>>> pq; void Dijkstra_1(int start, int id) { for (int i = 1; i <= n; i++) d[id][i] = INFL; d[id][start] = 0; pq.push({{0, start}, 1}); while (sz(pq)) { pair <pair <ll, int>, int> temp = pq.top(); pq.pop(); for (pair <pair <int, ll>, int> i : g[temp.fi.se]) { if (temp.fi.fi + i.fi.se < d[id][i.fi.fi]) { d[id][i.fi.fi] = temp.fi.fi + i.fi.se; pq.push({{temp.fi.fi + i.fi.se, i.fi.fi}, 1}); } } } } void Dijkstra_2(int start) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= 4; j++) d[j][i] = INFL; } d[1][start] = 0; pq.push({{0, start}, 1}); while (sz(pq)) { pair <pair <ll, int>, int> temp = pq.top(); pq.pop(); //cout << temp.fi.fi << sp << temp.fi.se << sp << temp.se << el; for (pair <pair <int, ll>, int> i : g[temp.fi.se]) { if ((temp.se == 1 && i.se == 4) || ((temp.se == 2 || temp.se == 3) && (i.se != 4 && i.se != temp.se)) || (temp.se == 4 && i.se != 4)) continue; if (temp.fi.fi + i.fi.se < d[i.se][i.fi.fi]) { d[i.se][i.fi.fi] = temp.fi.fi + i.fi.se; pq.push({{temp.fi.fi + i.fi.se, i.fi.fi}, i.se}); } } } } void Solve() { cin >> n >> m >> s >> t >> u >> v; for (int i = 1; i <= m; i++) { cin >> x[i] >> y[i] >> z[i]; g[x[i]].pub({{y[i], z[i]}, 1}); g[y[i]].pub({{x[i], z[i]}, 1}); } Dijkstra_1(s, 1); Dijkstra_1(t, 2); for (int i = 1; i <= m; i++) { g[x[i]].pub({{y[i], z[i]}, 4}); g[y[i]].pub({{x[i], z[i]}, 4}); if (d[1][x[i]] + z[i] + d[2][y[i]] == d[1][t]) { g[x[i]].pub({{y[i], 0}, 2}); g[y[i]].pub({{x[i], 0}, 3}); } else if (d[2][x[i]] + z[i] + d[1][y[i]] == d[1][t]) { g[y[i]].pub({{x[i], 0}, 2}); g[x[i]].pub({{y[i], 0}, 3}); } } Dijkstra_2(u); cout << min({d[1][v], d[2][v], d[3][v], d[4][v]}); } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(0); Solve(); return 0; } //coded by icyalmond
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...