제출 #722664

#제출 시각아이디문제언어결과실행 시간메모리
722664CookieCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
384 ms42780 KiB
#include<bits/stdc++.h> #include<fstream> using namespace std; ifstream fin("WINTER.inp"); ofstream fout("WINTER.out"); #define ll long long #define pb push_back #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> const int x[4] = {1, -1, 0, 0}; const int y[4] = {0, 0, 1, -1}; const ld PI = 3.14159265359; const ll mod = 1e9 + 7; const int mxn = 8e5 + 5; vt<pll>adj[mxn + 1]; int n, m, s, t, u, v; struct D{ int s; ll d[mxn + 1]; void go(int _s){ forr(i, 1, n + 1){ d[i] = 1e18; } s = _s; priority_queue<pll, vt<pll>, greater<pll>>pq; d[s] = 0; pq.push({d[s], s}); while(!pq.empty()){ auto [dd, u] = pq.top(); pq.pop(); if(d[u] != dd)continue; for(auto [v, w]: adj[u]){ if(d[v] > d[u] + w){ d[v] = d[u] + w; pq.push({d[v], v}); } } } } }; D U, V; ll res = 1e18; struct D2{ int s; ll d[mxn + 1], dp[2][mxn + 1]; void go(int _s, int t){ for(int i = 1; i <= n; i++){ d[i] = dp[0][i] = dp[1][i] = 1e18; } s = _s; priority_queue<pll, vt<pll>, greater<pll>>pq; d[s] = 0; pq.push({d[s], s}); dp[0][s] = U.d[s]; dp[1][s] = V.d[s]; while(!pq.empty()){ auto [dd, u] = pq.top(); pq.pop(); if(d[u] != dd)continue; for(auto [v, w]: adj[u]){ if(d[v] > d[u] + w){ dp[0][v] = min(dp[0][u], U.d[v]); dp[1][v] = min(dp[1][u], V.d[v]); d[v] = d[u] + w; pq.push({d[v], v}); }else if(d[v] == d[u] + w){ if(min(dp[0][u], U.d[v]) + min(dp[1][u], V.d[v]) < dp[0][v] + dp[1][v]){ dp[0][v] = min(dp[0][u], U.d[v]); dp[1][v] = min(dp[1][u], V.d[v]); } } } } res = min(res, dp[0][t] + dp[1][t]); } }; D2 S, T; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> s >> t >> u >> v; forr(i, 0, m){ int a, b, w; cin >> a >> b >> w; adj[a].pb(make_pair(b, w)); adj[b].pb(make_pair(a, w)); } U.go(u); V.go(v); res = U.d[v]; S.go(s, t); T.go(t, s); cout << res; return(0); }

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

commuter_pass.cpp: In member function 'void D::go(int)':
commuter_pass.cpp:37:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |             auto [dd, u] = pq.top(); pq.pop();
      |                  ^
commuter_pass.cpp:39:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |             for(auto [v, w]: adj[u]){
      |                      ^
commuter_pass.cpp: In member function 'void D2::go(int, int)':
commuter_pass.cpp:67:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |             auto [dd, u] = pq.top(); pq.pop();
      |                  ^
commuter_pass.cpp:69:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |             for(auto [v, w]: adj[u]){
      |                      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...