제출 #959751

#제출 시각아이디문제언어결과실행 시간메모리
959751OIaspirant2307Olympic Bus (JOI20_ho_t4)C++17
0 / 100
1053 ms3156 KiB
#include <iostream> #include <vector> #include <queue> #include <set> #include <utility> using namespace std; #define int long long #define pi pair<int, int> const int inf = 1e17; const int N = 203; vector<vector<int>> cost(N, vector<int>(N, inf)); vector<vector<int>> wt(N, vector<int>(N, inf)); vector<vector<int>> dist(N, vector<int>(N, inf)); multiset<pi> g[N]; int n, m; int dijkstra(int x, int y) { vector<int> dis(n + 1, inf); vector<bool> vis(n + 1, 0); multiset<pi> ms; ms.insert({0, x}); dis[x] = 0; while (!ms.empty()) { pi p = *ms.begin(); int v = p.second; if (vis[v]) { continue; } vis[v] = true; for (auto ch : g[v]) { int ch_v = ch.first; int ch_wt = ch.second; if (dis[v] + ch_wt < dis[ch_v]) { dis[ch_v] = dis[v] + ch_wt; ms.insert({dis[ch_v], ch_v}); } } } return dis[y]; } signed main() { cin >> n >> m; vector<pi> edges(m); for (int i = 0; i < m; i++) { int u, v, w, c; cin >> u >> v >> w >> c; if (g[u].size() < 2) g[u].insert({v, w}); edges[i] = {u, v}; cost[u][v] = min(cost[u][v], c); wt[u][v] = min(wt[u][v], w); } int ans = min(inf, dijkstra(1, n) + dijkstra(n, 1)); for (auto p : edges) { int i = p.first; int j = p.second; g[i].erase({j, wt[i][j]}); bool yes = g[j].count({i, wt[i][j]}); if (yes) { g[j].insert({i, wt[i][j]}); } ans = min(ans, dijkstra(1, n) + dijkstra(n, 1) + cost[i][j]); g[i].insert({j, wt[i][j]}); if (yes) { g[j].erase({i, wt[i][j]}); } } if (ans == inf) { cout << -1; return 0; } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...