제출 #674533

#제출 시각아이디문제언어결과실행 시간메모리
674533AmirAli_H1Commuter Pass (JOI18_commuter_pass)C++17
100 / 100
487 ms42760 KiB
// In the name of Allah #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define all(x) (x).begin(),(x).end() #define len(x) ((ll) (x).size()) #define F first #define S second #define pb push_back #define sep ' ' #define endl '\n' #define Mp make_pair #define debug(x) cerr << #x << ": " << x << endl; #define kill(x) cout << x << '\n', exit(0); #define set_dec(x) cout << fixed << setprecision(x); #define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout); int n, m; int s, t; int x, y; const int maxn = 2e5 + 4; const ll oo = 1e18; vector<pll> adj[maxn]; vector<pair<ll, pii>> E, Ex; ll dis[maxn]; bool mark[maxn]; ll D[maxn][2]; priority_queue<pll> qu; ll ans[maxn][3]; bool markx[maxn][3]; priority_queue<pair<ll, pii>> qux; void dij(int v) { fill(dis, dis + n, oo); fill(mark, mark + n, 0); dis[v] = 0; qu.push(Mp(-dis[v], v)); while (!qu.empty()) { v = qu.top().S; qu.pop(); if (mark[v]) continue; mark[v] = 1; for (auto f : adj[v]) { auto [u, w] = f; if (dis[v] + w < dis[u]) { dis[u] = dis[v] + w; qu.push(Mp(-dis[u], u)); } } } } void dij_ans(int v) { for (int i = 0; i < n; i++) { for (int T = 0; T < 3; T++) { ans[i][T] = oo; markx[i][T] = 0; } } for (int T = 0; T < 3; T++) { ans[v][T] = 0; qux.push(Mp(-ans[v][T], Mp(v, T))); } while (!qux.empty()) { auto [v, t] = qux.top().S; qux.pop(); if (markx[v][t]) continue; markx[v][t] = 1; for (auto f : adj[v]) { auto [u, w] = f; int tx = -1; if (t == 0) { if (w != 0) tx = 0; else tx = 1; } else if (t == 1) { if (w != 0) tx = 2; else tx = 1; } else { if (w != 0) tx = 2; } if (tx != -1 && ans[v][t] + w < ans[u][tx]) { ans[u][tx] = ans[v][t] + w; qux.push(Mp(-ans[u][tx], Mp(u, tx))); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; cin >> s >> t; s--; t--; cin >> x >> y; x--; y--; for (int i = 0; i < m; i++) { int u, v; ll w; cin >> u >> v >> w; u--; v--; adj[u].pb(Mp(v, w)); adj[v].pb(Mp(u, w)); E.pb(Mp(w, Mp(u, v))); } dij(s); for (int i = 0; i < n; i++) D[i][0] = dis[i]; dij(t); for (int i = 0; i < n; i++) D[i][1] = dis[i]; for (int i = 0; i < m; i++) { ll w = E[i].F; auto [u, v] = E[i].S; if (D[u][0] + w + D[v][1] == D[t][0]) { Ex.pb(Mp(0, Mp(u, v))); } if (D[v][0] + w + D[u][1] == D[t][0]) { Ex.pb(Mp(0, Mp(v, u))); } } ll output = oo; for (int T = 0; T < 2; T++) { for (auto f : Ex) { ll w = f.F; auto [u, v] = f.S; if (T == 1) swap(u, v); adj[u].pb(Mp(v, w)); } dij_ans(x); output = min(output, min(min(ans[y][0], ans[y][1]), ans[y][2])); for (auto f : Ex) { ll w = f.F; auto [u, v] = f.S; if (T == 1) swap(u, v); adj[u].pop_back(); } } cout << output << endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:136:7: warning: unused variable 'w' [-Wunused-variable]
  136 |    ll w = f.F; auto [u, v] = f.S;
      |       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...