제출 #623632

#제출 시각아이디문제언어결과실행 시간메모리
623632Do_you_copyCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
451 ms31600 KiB
#include <bits/stdc++.h> #define taskname "test" #define fi first #define se second #define int ll #define pb push_back #define faster ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; using ll = long long; using ull = unsigned ll; using ld = long double; using pii = pair <int, int>; using pil = pair <int, ll>; using pli = pair <ll, int>; using pll = pair <ll, ll>; mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count()); ll min(const ll &a, const ll &b){ return (a < b) ? a : b; } ll max(const ll &a, const ll &b){ return (a > b) ? a : b; } //const ll Mod = 1000000007; //const ll Mod2 = 999999999989; //only use when required const int maxN = 1e5 + 1; const ll inf = 1e15; int n, m; int s, t, x, y; ll dpx[maxN]; ll dpy[maxN]; vector <pii> adj[maxN]; vector <int> trace[maxN]; vector <int> dag[maxN]; bool visited[maxN]; int deg[maxN]; void Dijkstra(int s, vector <ll> &res, bool flag){ multiset <pii> S; fill(res.begin(), res.end(), inf); res[s] = 0; S.insert({0, s}); while (!S.empty()){ auto r = S.begin(); S.erase(S.begin()); if (res[r->se] != r->fi) continue; int u = r->se; for (const pii &i: adj[u]){ int v = i.fi; if (res[v] > res[u] + i.se){ res[v] = res[u] + i.se; S.insert({res[v], v}); if (flag){ trace[v].clear(); trace[v].pb(u); } } else if (res[v] == res[u] + i.se && flag){ trace[v].pb(u); } } } } void build_dag(int s){ queue <int> Q; Q.push(s); while (!Q.empty()){ int r = Q.front(); Q.pop(); if (visited[r]) continue; visited[r] = 1; for (int v: trace[r]){ dag[v].pb(r); if (!visited[v]){ Q.push(v); } } } } void Init(){ cin >> n >> m >> s >> t >> x >> y; for (int i = 1; i <= m; ++i){ int u, v, w; cin >> u >> v >> w; adj[u].pb({v, w}); adj[v].pb({u, w}); } vector <ll> d(n + 1), e(n + 1), f(n + 1); Dijkstra(t, d, 1); Dijkstra(x, e, 0); Dijkstra(y, f, 0); build_dag(s); for (int i = 1; i <= n; ++i){ } for (int i = 1; i <= n; ++i){ for (int j: dag[i]) ++deg[j]; dpx[i] = e[i]; dpy[i] = f[i]; } queue <int> Q; Q.push(t); ll ans = e[y]; while (!Q.empty()){ int u = Q.front(); Q.pop(); ans = min(ans, e[u] + dpy[u]); for (const int &i: dag[u]){ dpy[i] = min(dpy[i], dpy[u]); if (!--deg[i]){ Q.push(i); } } } for (int i = 1; i <= n; ++i){ for (int j: dag[i]) ++deg[j]; dpx[i] = e[i]; dpy[i] = f[i]; } Q.push(t); while (!Q.empty()){ int u = Q.front(); Q.pop(); ans = min(ans, dpx[u] + f[u]); for (const int &i: dag[u]){ dpx[i] = min(dpx[i], dpx[u]); if (!--deg[i]){ Q.push(i); } } } cout << ans; } signed main(){ if (fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } faster; ll tt = 1; //cin >> tt; while (tt--){ Init(); } }

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         freopen(taskname".out", "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...