Submission #1012280

#TimeUsernameProblemLanguageResultExecution timeMemory
1012280codefoxRobot (JOI21_ho_t4)C++14
0 / 100
952 ms116076 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #define int long long #define arr array<int, 5> #define pii pair<int, int> vector<vector<arr>> graph; int lim = 1e18; int32_t main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; graph.assign(n, vector<arr>()); vector<map<int, int>> cost(n); vector<map<int, int>> dist(n); vector<map<int, vector<pii>>> colour(n); vector<int> mn(n, lim); for (int j = 0; j < m; j++) { int a, b, c, d; cin >> a >> b >> c >> d; a--; b--; graph[a].push_back({b, c, d, 0, 0}); graph[b].push_back({a, c, d, 0, 0}); } for (int i = 0; i < n; i++) { for (arr ele:graph[i]) { cost[i][ele[1]] += ele[2]; dist[ele[0]][ele[1]] = lim; colour[i][ele[1]].push_back({ele[0], ele[2]}); } } priority_queue<arr, vector<arr>, greater<arr>> pq; pq.push({0, 0, 0, 0, 0}); while (pq.size()) { arr a = pq.top(); pq.pop(); int d = a[0]; int c = a[1]; int i = a[2]; int cc = a[4]; int pc = a[3]; if (mn[i]==lim) { for (arr ele:graph[i]) { pq.push({d+ele[2], 0, ele[0], ele[1], ele[2]}); } mn[i] = d; } if (c!=0) continue; if (dist[i][pc]<=d) continue; dist[i][pc] = d; if (c==0) { for (arr ele:graph[i]) { pq.push({d+cost[i][ele[1]]-ele[2], ele[1], ele[0], ele[1], ele[2]}); pq.push({d+cost[i][ele[1]], 0, ele[0], ele[1], ele[2]}); } for (pii ele:colour[i][pc]) { pq.push({d+cost[i][pc]-ele.second-cc, pc, ele.first, pc, ele.second}); pq.push({d+cost[i][pc]-cc, pc, 0, pc, ele.second}); } } } if (mn[n-1]>=lim) cout << -1; else cout << mn[n-1]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...