제출 #959496

#제출 시각아이디문제언어결과실행 시간메모리
959496OIaspirant2307Olympic Bus (JOI20_ho_t4)C++17
0 / 100
1080 ms3164 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)); vector<vector<bool>> done(N, vector<bool>(N, 0)); 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(m); 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[i] = {a, b}; } int ans = floyd(); for (auto p : v) { int i = p.first; int j = p.second; if (done[i][j]) continue; done[i][j] = true; 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...