#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';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
9 ms |
852 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
29 ms |
1832 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
9 ms |
980 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
9 ms |
852 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |