제출 #958465

#제출 시각아이디문제언어결과실행 시간메모리
958465BhavayGoyalOlympic Bus (JOI20_ho_t4)C++14
5 / 100
86 ms7664 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define vi vector<int> #define vii vector<vector<int>> #define pii pair<int, int> #define pb push_back #define f first #define s second #define endl "\n" const int linf = 1e15; // -------------------------------------------------- Main Code -------------------------------------------------- const int N = 201, M = 50001; int n, m, dist[N][N]; set<pii> g[N]; vii edges; map<pair<int, int>, bool> isShort; map<pii, pii> edge; pair<vi, vi> dijkstra(int source) { priority_queue<pii, vector<pii>, greater<>> q; vi vis(n+1, 0), dis(n+1, linf), par(n+1); q.push({0, source}); dis[source] = 0; while (!q.empty()) { pii f = q.top(); q.pop(); int src = f.s; if (vis[src]) continue; vis[src] = true; for (auto child : g[src]) { int ch = child.f, wt = child.s; if (dis[ch] > dis[src] + wt) { par[ch] = src; dis[ch] = dis[src] + wt; q.push({dis[ch], ch}); } } } return {dis, par}; } void sol() { for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dist[i][j] = linf; cin >> n >> m; for (int i = 1; i <= m; i++) { int a, b, c, d; cin >> a >> b >> c >> d; dist[a][b] = min(dist[a][b], c); g[a].insert({b, c}); edges.pb({a, b, c, d}); } pair<vi, vi> x = dijkstra(1); vi dis = x.f, par = x.s; int c = n; while (par[c]) { pii temp = edge[{par[c], c}]; isShort[{par[c], c}] = true; c = par[c]; } x = dijkstra(n); dis = x.f, par = x.s; c = 1; while (par[c]) { pii temp = edge[{par[c], c}]; isShort[{par[c], c}] = true; c = par[c]; } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) dist[i][j] = 0; dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } int ans = min(linf, dist[1][n] + dist[n][1]); for (auto i : edges) { int a = i[0], b = i[1], c = i[2], d = i[3]; if (isShort[{a, b}]) { int a = i[0], b = i[1], c = i[2], d = i[3]; g[a].erase({b, c}); g[b].insert({a, c}); pair<vi, vi> x = dijkstra(1); pair<vi, vi> y = dijkstra(n); ans = min(ans, x.f[n] + y.f[1] + d); g[b].erase({a, c}); g[a].insert({b, c}); } else { int new1n = dist[1][b] + c + dist[a][n]; int newn1 = dist[n][b] + c + dist[a][1]; ans = min(ans, dist[1][n] + newn1 + d); ans = min(ans, dist[n][1] + new1n + d); ans = min(ans, new1n + newn1 + d); } } cout << (ans==linf?-1:ans) << endl; } signed main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; // cin >> t; while (t--) { sol(); } return 0; }

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

ho_t4.cpp: In function 'void sol()':
ho_t4.cpp:61:13: warning: variable 'temp' set but not used [-Wunused-but-set-variable]
   61 |         pii temp = edge[{par[c], c}];
      |             ^~~~
ho_t4.cpp:69:13: warning: variable 'temp' set but not used [-Wunused-but-set-variable]
   69 |         pii temp = edge[{par[c], c}];
      |             ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...