제출 #1052815

#제출 시각아이디문제언어결과실행 시간메모리
1052815fauzCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
520 ms33256 KiB
#include <bits/stdc++.h> #define fi first #define se second #define int long long using namespace std; const int MAXN = 100001; typedef pair<int, int> II; typedef pair<long long, int> LLI; typedef pair<long long, II> LLII; int n, m, s, t, u, v; long long ds[MAXN], dt[MAXN]; vector<II> g[MAXN]; set<LLI> q; void dijk(int start, long long *d) { for (int i = 1; i <= n; ++i) d[i] = LLONG_MAX; q.clear(); d[start] = 0; q.insert(LLI(0, start)); while (!q.empty()) { int a = q.begin()->se; q.erase(q.begin()); for (II x : g[a]) { int b = x.fi, w = x.se; if (d[b] > d[a] + 1ll * w) { if (d[b] < LLONG_MAX) q.erase(LLI(d[b], b)); d[b] = d[a] + 1ll * w; q.insert(LLI(d[b], b)); } } } } set<LLII> sLII; long long d[4][MAXN]; long long get(int start, int stop) { for (int j = 0; j < 4; ++j) for (int i = 1; i <= n; ++i) d[j][i] = LLONG_MAX; sLII.clear(); d[0][start] = 0; sLII.insert(LLII(0, II(0, start))); while (!sLII.empty()) { int a = sLII.begin()->se.se, type = sLII.begin()->se.fi; sLII.erase(sLII.begin()); if (type < 3) { if (d[type + 1][a] > d[type][a] && (type == 2 || ds[a] + dt[a] == ds[t])) { if (d[type + 1][a] < LLONG_MAX) sLII.erase(LLII(d[type + 1][a], II(type + 1, a))); d[type + 1][a] = d[type][a]; sLII.insert(LLII(d[type + 1][a], II(type + 1, a))); } } for (II x : g[a]) { int b = x.fi, w = x.se; if (d[type][b] > d[type][a] + 1ll * w && (type == 0 || (type == 1 && ds[b] + dt[b] == ds[t]) || (type == 2 && ds[a] + w + dt[b] == ds[t]) || type == 3)) { if (d[type][b] < LLONG_MAX) sLII.erase(LLII(d[type][b], II(type, b))); d[type][b] = d[type][a] + 1ll * ((type == 2) ? 0 : w); sLII.insert(LLII(d[type][b], II(type, b))); } } } long long ans = LLONG_MAX; for (int j = 0; j < 4; ++j) ans = min(ans, d[j][stop]); return ans; } int32_t main() { if (fopen("inp.txt", "r")) { freopen("inp.txt", "r", stdin); freopen("out.txt", "w", stdout); } cin >> n >> m >> s >> t >> u >> v; for (int i = 1; i <= m; ++i) { int a, b, c; cin >> a >> b >> c; g[a].push_back(II(b, c)); g[b].push_back(II(a, c)); } dijk(s, ds); dijk(t, dt); cout << min(get(u, v), get(v, u)); }

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

commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen("inp.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...