Submission #959490

#TimeUsernameProblemLanguageResultExecution timeMemory
959490OIaspirant2307Olympic Bus (JOI20_ho_t4)C++17
0 / 100
1099 ms3280 KiB
#include <iostream> #include <vector> #include <utility> using namespace std; #define int long long #define pi pair<int, int> const int N = 203; int inf = 1e15; int dp[N][N]; vector<vector<int>> arr(N, vector<int>(N, inf)); vector<vector<int>> cost(N, vector<int>(N, -1)); vector<vector<int>> arr2(N, vector<int>(N, inf)); int n, m; int floyd() { for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { dp[i][j] = arr[i][j]; } } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]); } } } return min(dp[1][n] + dp[n][1], inf); } signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; for (int i = 0; i <= n; i++) { arr[i][i] = 0; } vector<pi> v; for (int i = 0; i < m; i++) { int a, b, c, d; cin >> a >> b >> c >> d; if (c < arr[a][b]) { arr2[a][b] = arr[a][b]; arr[a][b] = c; } cost[a][b] = d; v.push_back({a, b}); } int ans = floyd(); for (auto p : v) { int i = p.first; int j = p.second; int x = arr[j][i]; arr[j][i] = min(arr[j][i], arr[i][j]); arr[i][j] = arr2[i][j]; ans = min(ans, floyd() + cost[i][j]); arr[i][j] = arr[j][i]; arr[j][i] = x; } 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...