제출 #851767

#제출 시각아이디문제언어결과실행 시간메모리
851767chautanphatCommuter Pass (JOI18_commuter_pass)C++11
0 / 100
2 ms2652 KiB
#include <bits/stdc++.h> #define io freopen("input.inp", "r", stdin);freopen("output.out", "w", stdout); using namespace std; const int maxn = 1e5+1; int n; vector< pair<long long, int> > a[maxn]; vector<long long> dijkstra(int start) { vector<long long> d(n+1); d[start] = 0; priority_queue< pair<long long, int> > q; q.push(make_pair(0, start)); vector<bool> vs(n+1); while (q.size()) { int u = q.top().second; q.pop(); if (vs[u]) continue; vs[u] = 1; for (int i = 0; i < (int)a[u].size(); i++) { int v = a[u][i].first, w = a[u][i].second; if (d[u]+w < d[v]) { d[v] = d[u]+w; q.push(make_pair(-d[v], v)); } } } return d; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); io; int m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; a[u].push_back(make_pair(v, w)); a[v].push_back(make_pair(u, w)); } if (s == 0) { long long ans = 1e16; vector<long long> ds, dt, dv; ds = dijkstra(s), dt = dijkstra(t), dv = dijkstra(v); for (int i = 1; i <= n; i++) if (ds[i]+dt[i] == ds[t]) ans = min(ans, dv[i]); cout << ans; return 0; } vector< vector<long long> > d(n+1, vector<long long> (n+1, 1e16)); for (int i = 1; i <= n; i++) { d[i][i] = 0; for (int j = 0; j < (int)a[i].size(); j++) d[i][a[i][j].first] = a[i][j].second; } for (int k = 1; k <= n; k++) for (int u = 1; u <= n; u++) for (int v = 1; v <= n; v++) d[u][v] = min(d[u][v], d[u][k]+d[k][v]); long long ans = 1e16; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (d[s][i]+d[i][j]+d[j][t] == d[s][t]) ans = min(ans, d[u][i]+d[j][v]); cout << ans; return 0; }

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:2:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define io freopen("input.inp", "r", stdin);freopen("output.out", "w", stdout);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:43:5: note: in expansion of macro 'io'
   43 |     io;
      |     ^~
commuter_pass.cpp:2:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define io freopen("input.inp", "r", stdin);freopen("output.out", "w", stdout);
      |                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:43:5: note: in expansion of macro 'io'
   43 |     io;
      |     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...