제출 #678618

#제출 시각아이디문제언어결과실행 시간메모리
678618SanguineChameleonCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
274 ms20416 KiB
// BEGIN BOILERPLATE CODE #include <bits/stdc++.h> using namespace std; #ifdef KAMIRULEZ const bool kami_loc = true; const long long kami_seed = 69420; #else const bool kami_loc = false; const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count(); #endif const string kami_fi = "kamirulez.inp"; const string kami_fo = "kamirulez.out"; mt19937_64 kami_gen(kami_seed); long long rand_range(long long rmin, long long rmax) { uniform_int_distribution<long long> rdist(rmin, rmax); return rdist(kami_gen); } long double rand_real(long double rmin, long double rmax) { uniform_real_distribution<long double> rdist(rmin, rmax); return rdist(kami_gen); } void file_io(string fi, string fo) { if (fi != "" && (!kami_loc || fi == kami_fi)) { freopen(fi.c_str(), "r", stdin); } if (fo != "" && (!kami_loc || fo == kami_fo)) { freopen(fo.c_str(), "w", stdout); } } void set_up() { if (kami_loc) { file_io(kami_fi, kami_fo); } ios_base::sync_with_stdio(0); cin.tie(0); } void just_do_it(); void just_exec_it() { if (kami_loc) { auto pstart = chrono::steady_clock::now(); just_do_it(); auto pend = chrono::steady_clock::now(); long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count(); string bar(50, '='); cout << '\n' << bar << '\n'; cout << "Time: " << ptime << " ms" << '\n'; } else { just_do_it(); } } int main() { set_up(); just_exec_it(); return 0; } // END BOILERPLATE CODE // BEGIN MAIN CODE const long long inf = 1e18L + 20; const int ms = 1e5 + 20; vector<pair<int, int>> adj[ms]; long long d_sx[ms]; long long d_tx[ms]; long long d_ty[ms]; long long dp_tx[ms]; long long dp_ty[ms]; bool g1[ms]; bool g2[ms]; bool g3[ms]; bool f[ms]; int n, m, sx, sy, tx, ty; void dijk(int cx, long long d[]) { for (int i = 1; i <= n; i++) { d[i] = inf; } d[cx] = 0; priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q; q.push({0, cx}); while (!q.empty()) { int u = q.top().second; long long cd = q.top().first; q.pop(); if (d[u] != cd) { continue; } for (auto x: adj[u]) { int v = x.first; int w = x.second; if (d[u] + w < d[v]) { d[v] = d[u] + w; q.push({d[v], v}); } } } } void dfs1(int u) { if (u == sy) { f[u] = true; return; } for (auto x: adj[u]) { int v = x.first; int w = x.second; if (d_sx[u] + w == d_sx[v]) { if (!g3[v]) { dfs1(v); g3[v] = true; } f[u] |= f[v]; } } } void dfs2(int u, long long dp[], long long d[], bool g[]) { dp[u] = d[u]; if (u == sy) { return; } for (auto x: adj[u]) { int v = x.first; int w = x.second; if (d_sx[u] + w == d_sx[v]) { if (f[v]) { if (!g[v]) { dfs2(v, dp, d, g); g[v] = true; } dp[u] = min(dp[u], dp[v]); } } } } void just_do_it() { cin >> n >> m; cin >> sx >> sy >> tx >> ty; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } dijk(sx, d_sx); dijk(tx, d_tx); dijk(ty, d_ty); dfs1(sx); dfs2(sx, dp_tx, d_tx, g1); dfs2(sx, dp_ty, d_ty, g2); long long res = d_tx[ty]; for (int u = 1; u <= n; u++) { if (f[u]) { res = min(res, dp_tx[u] + d_ty[u]); res = min(res, dp_ty[u] + d_tx[u]); } } cout << res; } // END MAIN CODE

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

commuter_pass.cpp: In function 'void file_io(std::string, std::string)':
commuter_pass.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   freopen(fi.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   freopen(fo.c_str(), "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...