Submission #1012263

#TimeUsernameProblemLanguageResultExecution timeMemory
1012263codefoxRobot (JOI21_ho_t4)C++14
0 / 100
3043 ms293720 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; vector<vector<int>> fc; vector<int> d1; vector<int> d2; vector<int> d3; vector<int> d4; 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>> mn(n); vector<map<int, vector<int>>> cc(n); fc.assign(n, vector<int>()); d1.assign(n, lim); d2.assign(n, lim); d3.assign(n, lim); d4.assign(n, lim); for (int j = 0; j < m; j++) { int a, b, c, d; cin >> a >> b >> c >> d; a--; b--; c--; 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]; mn[i][ele[1]] = lim; cc[i][ele[1]].push_back(ele[0]); } } priority_queue<arr, vector<arr>, greater<arr>> pq; pq.push({0, 0, 0, -1, 0}); pq.push({0, 1, 0, -1, 0}); pq.push({0, 2, 0, -1, 0}); pq.push({0, 3, 0, -1, 0}); while (pq.size()) { arr a = pq.top(); pq.pop(); int d = a[0]; int c = a[1]; int i = a[2]; int p = a[3]; int pc = a[4]; if (pc == -1) { if (mn[i][c]<=d) continue; mn[i][c]=d; for (int ele:cc[i][c]) { pq.push({d, c, ele, p, 0}); } continue; } if (d4[i]<=d) continue; int b = 0; for (int ele:fc[i]) { if (ele ==c) b=1; } if (b) continue; fc[i].push_back(c); if (d1[i]==lim) d1[i] = d; else if (d2[i]==lim) d2[i] = d; else if (d3[i]==lim) d3[i] = d; else if (d4[i]==lim) d4[i] = d; int ava1 = -1; int ava2 = -1; int avac1 = 0; int avac2 = 0; for (int j = 0; j < m; j++) { if (cost[i][j]==0) { if (ava1==-1) ava1 = j; else if (ava2==-1) { ava2 = j; break; } } } if (ava1==-1) avac1=lim; if (ava2==-1) avac2=lim; for (arr ele:graph[i]) { if (cost[i][ele[1]]<avac1) { ava2 = ava1; avac2 = avac1; avac1=cost[i][ele[1]]; ava1=ele[1]; } else if (cost[i][ele[1]]<avac2) { ava2 = ele[1]; avac2=cost[i][ele[1]]; } } for (arr ele:graph[i]) { if (ele[0]==p) continue; pq.push({d+cost[i][ele[1]]-ele[2], ele[1], ele[0], i, ele[1]}); pq.push({d+avac1+ele[2], ava1, ele[0], i, ele[1]}); pq.push({d+avac2+ele[2], ava2, ele[0], i, ele[1]}); pq.push({d+avac1+cost[ele[0]][ava1], ava1, ele[0], i, -1}); pq.push({d+avac2+cost[ele[0]][ava2], ava2, ele[0], i, -1}); } } if (d1[n-1]>=lim) cout << -1; else cout << d1[n-1]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...