제출 #757520

#제출 시각아이디문제언어결과실행 시간메모리
757520Desh03Olympic Bus (JOI20_ho_t4)C++17
0 / 100
29 ms1832 KiB
#include <bits/stdc++.h> using namespace std; const long long INF = 1e18; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<vector<long long>> dp(n, vector<long long> (n, INF)), e = dp; vector<tuple<int, int, int, int>> edges; for (int i = 0; i < n; i++) dp[i][i] = 0; for (int i = 0; i < m; i++) { int u, v, c, d; cin >> u >> v >> c >> d; --u, --v; if (c < dp[u][v]) e[u][v] = dp[u][v], dp[u][v] = c; else if (c < e[u][v]) e[u][v] = c; } for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]); long long ans = INF; for (auto [u, v, c, d] : edges) { ans = min(ans, dp[0][v] + dp[u][n - 1] + dp[n - 1][0] + d); ans = min(ans, dp[0][n - 1] + dp[n - 1][v] + dp[u][0] + d); } cout << (ans == INF ? -1 : 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...