제출 #971478

#제출 시각아이디문제언어결과실행 시간메모리
971478shezittCommuter Pass (JOI18_commuter_pass)C++14
24 / 100
103 ms262144 KiB
#include <iostream> #include <vector> #include <algorithm> #include <numeric> #include <cassert> #include <queue> #include <set> using namespace std; using ll = long long; #define int ll #define fore(a, b, c) for(int a=b; a<c; ++a) #define sz(x) (int) x.size() #define all(x) x.begin(), x.end() #define vi vector<int> #define ii pair<int,int> #define F first #define S second const int MAXN = 1010; vector<ii> adj[MAXN]; int n, m, s, t, u, v; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; cin >> s >> t; cin >> u >> v; vector<vi> d(n+1, vi(n+1, 4e18)); fore(i, 0, m){ int x, y, c; cin >> x >> y >> c; adj[x].push_back({y, c}); adj[y].push_back({x, c}); d[x][y] = d[y][x] = c; } fore(i, 1, n+1){ d[i][i] = 0; } auto dijkstra = [&](int r, vi &dis) -> void { dis[r] = 0; priority_queue<ii, vector<ii>, greater<ii>> pq; pq.push({0, r}); while(sz(pq)){ auto [cost, node] = pq.top(); pq.pop(); if(cost != dis[node]) continue; for(auto [to, c] : adj[node]){ if(dis[node] + c < dis[to]){ dis[to] = dis[node] + c; pq.push({dis[to], to}); } } } }; // fore(i, 1, n+1){ // dijkstra(i, d[i]); // } // floyd-warshal fore(k, 1, n+1){ fore(i, 1, n+1){ fore(j, 1, n+1){ d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } int ans = d[u][v]; fore(xx, 1, n+1){ fore(yy, 1, n+1){ int x = xx, y = yy; if(d[s][y] < d[s][x]) swap(x, y); if(d[s][x] + d[x][y] != d[s][y]) continue; if(d[s][x] + d[x][y] + d[y][t] != d[s][t]) continue; int res = min(d[u][x] + d[v][y], d[v][x] + d[u][y]); ans = min(ans, res); } } cout << ans; }

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

commuter_pass.cpp: In lambda function:
commuter_pass.cpp:56:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |             auto [cost, node] = pq.top();
      |                  ^
commuter_pass.cpp:61:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |             for(auto [to, c] : adj[node]){
      |                      ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:51:10: warning: variable 'dijkstra' set but not used [-Wunused-but-set-variable]
   51 |     auto dijkstra = [&](int r, vi &dis) -> void {
      |          ^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...