제출 #1087598

#제출 시각아이디문제언어결과실행 시간메모리
1087598pqthangvCommuter Pass (JOI18_commuter_pass)C++11
0 / 100
4 ms6748 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, l, r) for(int i = (l); i <= (r); ++i) #define FORD(i, r, l) for(int i = (r); i >= (l); --i) #define REP(i, l, r) for(int i = (l); i < (r); ++i) #define pb push_back #define fi first #define se second #define el '\n' #define ll long long #define all(v) v.begin(), v.end() #define compact(v) v.erase(unique(all(v)), end(v)) const int maxN = 1e5 + 5; const int MOD = 1e9 + 7; const ll INF = 1e18; struct Edges { int u, v; ll cost; Edges(int _u = 0, int _v = 0, ll _c = 0) : u(_u), v(_v), cost(_c) {} } b[maxN]; int n, m, s, t, u, v; vector< pair <int, ll> > adj[maxN]; vector < int > g[maxN]; ll dist[5][maxN], fu[maxN], fv[maxN], ans; bool vis[maxN]; void dijk(int start, int type) { priority_queue< pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll, int> > > pq; FOR(i, 1, n) dist[type][i] = INF; dist[type][start] = 0; pq.push(make_pair(0, start)); while(!pq.empty()) { int u = pq.top().se; ll cost = pq.top().fi; pq.pop(); if (cost > dist[type][u]) continue; for(pair <int, ll> s : adj[u]) { int v = s.fi; ll cost = s.se; if (dist[type][v] > dist[type][u] + cost) { dist[type][v] = dist[type][u] + cost; pq.push(make_pair(dist[type][v], v)); } } } } void build(int u){ vis[u] = true; for(auto [v, wv] : adj[u]){ if(dist[1][u] + wv + dist[2][v] == dist[1][t]){ g[u].pb(v); if(!vis[v]) build(v); } } } void dfs(int start) { fu[start] = dist[3][start]; fv[start] = dist[4][start]; vis[start] = 1; for(int child : g[start]) { if (vis[child] == false) { dfs(child); } fu[start] = min(fu[start], fu[child]); fv[start] = min(fv[start], fv[child]); } // cout << start << " " << dist[3][start] + fv[start] << " " << dist[4][start] + fu[start] << el; ans = min(ans, dist[3][start] + fv[start]); ans = min(ans, dist[4][start] + fu[start]); } void etoile() { cin >> n >> m >> s >> t >> u >> v; FOR(i, 1, m) { int u, v; ll c; cin >> u >> v >> c; adj[u].pb(make_pair(v, c)); adj[v].pb(make_pair(u, c)); b[i] = Edges(u, v, c); } dijk(s, 1); dijk(t, 2); dijk(u, 3); dijk(v, 4); // build dag build(s); memset(vis, 0, sizeof(vis)); ans = dist[3][v]; // FOR(i, 1, 4) { // FOR(j, 1, n) { // cout << dist[i][j] << el; // } // cout << el; // } dfs(s); cout << ans << el; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); #define cecilia "bus" freopen(cecilia".inp", "r", stdin); freopen(cecilia".out", "w", stdout); etoile(); return 0; } /* 5 6 1 3 4 5 1 2 10 1 3 30 1 4 15 2 3 10 4 3 5 3 5 10 */

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

commuter_pass.cpp: In function 'void build(int)':
commuter_pass.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for(auto [v, wv] : adj[u]){
      |              ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:119:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |     freopen(cecilia".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:120:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |     freopen(cecilia".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...