제출 #631252

#제출 시각아이디문제언어결과실행 시간메모리
631252colossal_pepeOlympic Bus (JOI20_ho_t4)C++17
5 / 100
1093 ms2132 KiB
#include <iostream> #include <vector> #include <queue> #include <tuple> using namespace std; using ll = long long; const ll INF = 1e18; int n, m; vector<tuple<int, int, ll, ll>> edges; vector<vector<int>> g; ll bfs(int start, int flipped) { ll dp[n]; for (int i = 0; i < n; i++) { dp[i] = -INF; } priority_queue<tuple<ll, int>> pq; dp[start] = 0; pq.push({0, start}); while (not pq.empty()) { auto [dist, u] = pq.top(); pq.pop(); if (dp[u] != dist) continue; for (int e : g[u]) { auto [a, b, c, d] = edges[e]; if (flipped == e) swap(a, b); if (dist - c > dp[b]) { dp[b] = dist - c; pq.push({dist - c, b}); } } } return -dp[start ? 0 : n - 1]; } ll solve(int flipped) { return bfs(0, flipped) + bfs(n - 1, flipped) + get<3>(edges[flipped]); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; g.resize(n), edges.resize(m + 1); auto &[a, b, c, d] = edges[0]; a = b = -1; c = d = 0; for (int i = 1; i <= m; i++) { auto &[a, b, c, d] = edges[i]; cin >> a >> b >> c >> d; a--, b--; g[a].push_back(i); g[b].push_back(i); } ll ans = INF; for (int i = 0; i <= m; i++) { ans = min(ans, solve(i)); } cout << (ans != INF ? ans : -1) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...