제출 #1093492

#제출 시각아이디문제언어결과실행 시간메모리
1093492anhthiCommuter Pass (JOI18_commuter_pass)C++14
15 / 100
209 ms29388 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define mp(x, y) make_pair(x, y) #define sz(v) ((int) (v).size()) #define all(v) (v).begin(), (v).end() #define MASK(i) (1LL << (i)) #define BIT(x, y) (((x) >> (y)) & 1) #define pb push_back #define max_rng *max_element #define min_rng *min_element #define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i) #define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) #define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i) template <class X, class Y> inline bool maximize(X &x, Y y) { return (x < y ? x = y, true : false); } template <class X, class Y> inline bool minimize(X &x, Y y) { return (x > y ? x = y, true : false); } template <class X> inline void compress(vector<X> &a) { sort(all(a)); a.resize(unique(all(a)) - a.begin()); } int ctz(ll x) { return __builtin_ctzll(x); } int lg(ll x) { return 63 - __builtin_clzll(x); } int popcount(ll x) { return __builtin_popcount(x); } mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll rand(ll l, ll r) { return l + abs((ll) rng()) % (r - l + 1); } const ll oo = (ll) 1e17; const int inf = (ll) 2e9 + 7, mod = (ll) 1e9 + 7; const int mxn = 2e5 + 5, mxm = 3e2 + 5; const int LG = 18, BASE = 311, BLOCK = 350; void add(int &x, int y) { x += y; if (x >= mod) x -= mod; } void sub(int &x, int y) { x -= y; if (x < 0) x += mod; } int n, m; int s, t, u, v; struct Edge { int u, v, w; } e[mxn]; vector<pair<int, int>> g[mxn]; vector<int> dag[mxn]; ll dist_u[mxn], dist_v[mxn]; void calc(int s, ll dp[]) { fill(dp, dp + n + 1, oo); priority_queue<pair<ll, int>> pq; dp[s] = 0; pq.push(mp(0, s)); while (!pq.empty()) { pair<ll, int> top = pq.top(); pq.pop(); int u = top.se; ll dist = -top.fi; if (dp[u] != dist) continue; for (pair<int, int> i : g[u]) { ll d = dist + e[i.second].w; if (minimize(dp[i.first], d)) { pq.push(mp(-d, i.first)); } } } return; } ll f[mxn]; struct Path { ll dist; int u, par; bool operator < (const Path &p) const { return dist > p.dist; } }; ll dpU[mxn], dpV[mxn]; ll dijkstra(int s, int t) { fill(f, f + 1 + n, oo); fill(dpU, dpU + 1 + n, oo); fill(dpV, dpV + 1 + n, oo); priority_queue<Path> pq; f[s] = 0; pq.push({0, s, 0}); while (!pq.empty()) { Path top = pq.top(); pq.pop(); if (f[top.u] != top.dist) continue; dpU[top.u] = min(dist_u[top.u], dpU[top.par]); dpV[top.u] = min(dist_v[top.u], dpV[top.par]); for (pair<int, int> i : g[top.u]) { if (minimize(f[i.first], top.dist + e[i.second].w)) { pq.push({top.dist + e[i.second].w, i.first, top.u}); } else if (f[i.first] == top.dist + e[i.second].w) { if (min(dist_u[i.first], dpU[top.u]) + min(dist_v[top.u], dpV[top.u]) <= dpU[i.first] + dpV[i.first]) { dpU[i.first] = min(dist_u[i.first], dpU[top.u]); dpV[i.first] = min(dist_v[i.first], dpV[top.u]); } } } } return dpU[t] + dpV[t]; } int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define TASK "cquery" if (fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } cin >> n >> m; cin >> s >> t >> u >> v; rep(i, m) { int u, v, w; cin >> u >> v >> w; e[i] = {u, v, w}; g[u].pb(mp(v, i)); g[v].pb(mp(u, i)); } calc(u, dist_u); calc(v, dist_v); ll ans = dist_u[v]; minimize(ans, dijkstra(s, t)); minimize(ans, dijkstra(t, s)); cout << ans; return 0; }

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

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