제출 #1111292

#제출 시각아이디문제언어결과실행 시간메모리
1111292injeolmiCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
275 ms24020 KiB
#include <bits/stdc++.h> #define int ll #define FOR(i,k,n) for(int i = k; i <= n; i++) #define FORR(i,k,n) for(int i = n; i >= k; i--) #define pb push_back #define all(x) begin(x),end(x) #define fi first #define se second #define BIT(S, i) (((S)>>(i))&1) #define MASK(i) ((1ll)<<(i)) #define name "loopy" using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef long double ld; template<class X, class Y> bool maximize(X &a, Y b) { if (a < b) {a = b; return true;} return false; } template<class X, class Y> bool minimize(X &a, Y b) { if (a > b) {a = b; return true;} return false; } const int N = 1e5+6; const int INF = 1e18; int m, n, s, t, u, v, ans; vector<pii> adj[N]; vi dist1, dist2, dp1, dp2, d; void dijkstra(vi &di, int s) { di.assign(N, INF); di[s] = 0; priority_queue<pii, vector<pii>, greater<pii>> q; q.push({0, s}); while (q.size()) { auto [du, u] = q.top(); q.pop(); if (du != di[u]) continue; for (auto [v, w] : adj[u]) { if (di[v] > di[u] + w) { di[v] = di[u] + w; q.push({di[v], v}); } } } } int dijkstra2(int s, int t) { d.assign(N, INF); dp1.assign(N, INF); dp2.assign(N, INF); priority_queue<pii, vector<pii>, greater<pii>> q; q.push({0, s}); d[s] = 0; dp1[s] = dist1[s]; dp2[s] = dist2[s]; while (q.size()) { auto [du, u] = q.top(); q.pop(); if (du != d[u]) continue; for (auto [v, w] : adj[u]) { if (d[v] > d[u] + w) { d[v] = d[u] + w; q.push({d[v], v}); dp1[v] = min(dist1[v], dp1[u]); dp2[v] = min(dist2[v], dp2[u]); } else if (d[v] == d[u] + w) { int minV = min(dp2[u], dist2[v]); int minU = min(dp1[u], dist1[v]); if (minU + minV <= dp1[v] + dp2[v]) { dp1[v] = minU; dp2[v] = minV; } } } } return dp1[t] + dp2[t]; } void solve() { FOR(i,0,N-1) adj[i].clear(); cin >> n >> m >> s >> t >> u >> v; while (m--) { int x, y, z; cin >> x >> y >> z; adj[x].pb({y, z}); adj[y].pb({x, z}); } dijkstra(dist1, u); dijkstra(dist2, v); ans = dist1[v]; minimize(ans, dijkstra2(s,t)); minimize(ans, dijkstra2(t,s)); cout << ans << '\n'; } main(){ ios_base::sync_with_stdio(0); cin.tie(0); if (fopen(name".inp","r")) { freopen(name".inp","r",stdin); freopen(name".out","w",stdout); } solve(); }

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

commuter_pass.cpp: In function 'void dijkstra(vi&, ll)':
commuter_pass.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |         auto [du, u] = q.top(); q.pop();
      |              ^
commuter_pass.cpp:47:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |         for (auto [v, w] : adj[u]) {
      |                   ^
commuter_pass.cpp: In function 'll dijkstra2(ll, ll)':
commuter_pass.cpp:65:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |         auto [du, u] = q.top(); q.pop();
      |              ^
commuter_pass.cpp:67:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |         for (auto [v, w] : adj[u]) {
      |                   ^
commuter_pass.cpp: At global scope:
commuter_pass.cpp:105:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  105 | main(){
      | ^~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(name".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...