제출 #1167569

#제출 시각아이디문제언어결과실행 시간메모리
1167569kunzaZa183Olympic Bus (JOI20_ho_t4)C++20
5 / 100
1095 ms7120 KiB
#include <bits/stdc++.h> using namespace std; #define int long long signed main() { cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; vector<vector<int>> elist; elist.push_back({0, 0, 0, 0}); for (int i = 0; i < m; i++) { int a, b, c, d; cin >> a >> b >> c >> d; a--, b--; elist.push_back({a, b, c, d}); } int minans = INT_MAX; for (int i = 0; i <= m; i++) { vector<vector<pair<int, int>>> adj(n, vector<pair<int, int>>()); int curp = elist[i][3]; swap(elist[i][0], elist[i][1]); // cout << "ELIST\n"; // for (auto a : elist) { // for (auto b : a) cout << b << " "; // cout << "\n"; // } for (int j = 0; j <= m; j++) { adj[elist[j][0]].emplace_back(elist[j][1], elist[j][2]); } vector<int> visited(n, INT_MAX); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pqpii; pqpii.emplace(0, 0); while (!pqpii.empty()) { pair<int, int> cur = pqpii.top(); pqpii.pop(); if (visited[cur.second] != INT_MAX) continue; visited[cur.second] = cur.first; for (auto a : adj[cur.second]) pqpii.emplace(a.second + cur.first, a.first); } curp += visited[n - 1]; // cout<<curp<<"\n"; pqpii.emplace(0, n - 1); visited = vector<int>(n, INT_MAX); while (!pqpii.empty()) { pair<int, int> cur = pqpii.top(); pqpii.pop(); // cout<<cur.first<<" "<<cur.second<<"\n"; if (visited[cur.second] != INT_MAX) continue; visited[cur.second] = cur.first; for (auto a : adj[cur.second]) pqpii.emplace(a.second + cur.first, a.first); } curp += visited[0]; // cout<<curp<<"\n"; minans = min(minans, curp); swap(elist[i][0], elist[i][1]); } if (minans == INT_MAX) cout << "-1\n"; else cout << minans << "\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...