제출 #750962

#제출 시각아이디문제언어결과실행 시간메모리
750962nononoCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
395 ms40776 KiB
#include "bits/stdc++.h" #define int long long using namespace std; const int inf = 1e18; const int mxN = 1e5 + 10; int n, m, s, t, U, V; vector<vector<pair<int, int>>> adj(mxN); vector<vector<int>> d(5, vector<int> (mxN)); void SP(int type, int x){ priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for(int i = 1; i <= n; i ++){ d[type][i] = inf; } d[type][x] = 0; pq.push({0, x}); while(!pq.empty()){ int du = pq.top().first; int u = pq.top().second; pq.pop(); if(d[type][u] != du) continue ; for(auto [v, w] : adj[u]){ if(d[type][v] > du + w){ d[type][v] = du + w; pq.push({d[type][v], v}); } } } } int Res; int check[mxN], mark[mxN]; int M1[mxN], M2[mxN]; vector<vector<int>> k(mxN); void dfs(int u){ check[u] = 1; M1[u] = d[1][u]; M2[u] = d[2][u]; for(int v : k[u]){ if(check[v] == 0) dfs(v); if(mark[v] == 1){ mark[u] = 1; M1[u] = min(M1[u], M1[v]); M2[u] = min(M2[u], M2[v]); } } Res = min({Res, d[1][u] + M2[u], d[2][u] + M1[u]}); } signed main(){ #define name "test" if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> s >> t >> U >> V; vector<array<int, 3>> edges; for(int i = 1; i <= m; i ++){ int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); edges.push_back({u, v, w}); } SP(0, s); SP(1, U); SP(2, V); for(auto [u, v, w] : edges){ if(d[0][u] + w == d[0][v]) k[u].push_back(v); if(d[0][v] + w == d[0][u]) k[v].push_back(u); } mark[t] = 1; for(int i = 1; i <= n; i ++){ M1[i] = M2[i] = inf; } Res = d[1][V]; dfs(s); cout << Res << "\n"; return 0; }

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

commuter_pass.cpp: In function 'void SP(long long int, long long int)':
commuter_pass.cpp:29:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |         for(auto [v, w] : adj[u]){
      |                  ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:88:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |     for(auto [u, v, w] : edges){
      |              ^
commuter_pass.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         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...