제출 #958780

#제출 시각아이디문제언어결과실행 시간메모리
958780AlperenTOlympic Bus (JOI20_ho_t4)C++17
16 / 100
1088 ms3772 KiB
#include <bits/stdc++.h> using namespace std; const int INF = 2e9; int n, m, ans = INF; vector<vector<pair<int, int>>> normalgraph, revgraph, brutegraph; vector<int> a, b, c, d, from1, to1, fromn, ton; vector<bool> isinsp; void dijkstra(int x, vector<int> &dist, vector<vector<pair<int, int>>> &graph){ vector<bool> vis(n + 1, false); vector<int> par(n + 1, -1); dist.assign(n + 1, INF); dist[x] = 0; while(true){ int v = -1; for(int i = 1; i <= n; i++){ if(!vis[i] && dist[i] != INF && (v == -1 || dist[i] < dist[v])){ v = i; } } if(v == -1) break; if(par[v] != -1) isinsp[par[v]] = true; vis[v] = true; for(auto [u, i] : graph[v]){ if(dist[v] + c[i] < dist[u]){ dist[u] = dist[v] + c[i]; par[u] = i; } } } } int main() { ios_base::sync_with_stdio(false);cin.tie(NULL); cin >> n >> m; normalgraph = revgraph = vector(n + 1, vector<pair<int, int>>{}); a = b = c = d = vector(m + 1, 0); isinsp = vector(m + 1, false); for(int i = 1; i <= m; i++){ cin >> a[i] >> b[i] >> c[i] >> d[i]; normalgraph[a[i]].push_back({b[i], i}); revgraph[b[i]].push_back({a[i], i}); } dijkstra(1, from1, normalgraph); dijkstra(1, to1, revgraph); dijkstra(n, fromn, normalgraph); dijkstra(n, ton, revgraph); if(from1[n] != INF && fromn[1] != INF) ans = from1[n] + fromn[1]; for(int i = 1; i <= m; i++){ int useton = INF, useto1 = INF; if(isinsp[i]){ brutegraph = vector(n + 1, vector<pair<int, int>>{}); for(int j = 1; j <= m; j++){ if(j == i) brutegraph[b[j]].push_back({a[j], j}); else brutegraph[a[j]].push_back({b[j], j}); } vector<int> brutedist; dijkstra(1, brutedist, brutegraph); useton = brutedist[n]; dijkstra(n, brutedist, brutegraph); useto1 = brutedist[1]; } else{ useton = from1[n], useto1 = fromn[1]; if(from1[b[i]] != INF && ton[a[i]] != INF) useton = min(useton, from1[b[i]] + c[i] + ton[a[i]]); if(fromn[b[i]] != INF && to1[a[i]] != INF) useto1 = min(useto1, fromn[b[i]] + c[i] + to1[a[i]]); } if(useton != INF && useto1 != INF) ans = min(ans, d[i] + useton + useto1); } cout << (ans == INF ? -1 : ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...