Submission #522280

#TimeUsernameProblemLanguageResultExecution timeMemory
522280AdamGSRobot (JOI21_ho_t4)C++17
100 / 100
2944 ms134636 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=1e5+7; const ll INF=1e18+7; vector<pair<int,pair<int,int>>>V[LIM]; ll odl[LIM], koszt[2*LIM], kolor[2*LIM]; map<pair<int,int>,int>odw; map<pair<int,int>,ll>sum, ma1, ma2, ind1, ind2; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; rep(i, m) { int a, b; cin >> a >> b >> kolor[i] >> koszt[i]; --a; --b; V[a].pb({kolor[i], {i, b}}); V[b].pb({kolor[i], {i, a}}); sum[{a, kolor[i]}]+=koszt[i]; sum[{b, kolor[i]}]+=koszt[i]; rep(j, 2) { if(koszt[i]>=ma1[{a, kolor[i]}]) { ma2[{a, kolor[i]}]=ma1[{a, kolor[i]}]; ind2[{a, kolor[i]}]=ind1[{a, kolor[i]}]; ma1[{a, kolor[i]}]=koszt[i]; ind1[{a, kolor[i]}]=i; } else if(koszt[i]>=ma2[{a, kolor[i]}]) { ma2[{a, kolor[i]}]=koszt[i]; ind2[{a, kolor[i]}]=i; } swap(a, b); } } rep(i, n) { odl[i]=INF; sort(all(V[i])); } priority_queue<pair<ll,pair<int,int>>>q; q.push({0, {0, -1}}); while(!q.empty()) { ll o=-q.top().st, p=q.top().nd.st, lst=q.top().nd.nd; q.pop(); if(odw[{p, lst}]) continue; odw[{p, lst}]=1; if(odl[p]==INF) { odl[p]=o; for(auto i : V[p]) { if(!odw[{i.nd.nd, i.nd.st}]) q.push({-o-koszt[i.nd.st], {i.nd.nd, i.nd.st}}); if(!odw[{i.nd.nd, -1}]) q.push({-o-sum[{p, i.st}]+koszt[i.nd.st], {i.nd.nd, -1}}); } } if(lst==-1) continue; if(ind1[{p, kolor[lst]}]==lst) { if(ma2[{p, kolor[lst]}]) { pair<int,pair<int,int>>xd={kolor[lst], {ind2[{p, kolor[lst]}], -1}}; auto it=lower_bound(all(V[p]), xd); int x=it-V[p].begin(); if(!odw[{V[p][x].nd.nd, -1}]) { q.push({-o-sum[{p, kolor[lst]}]+koszt[lst]+ma2[{p, kolor[lst]}], {V[p][x].nd.nd, -1}}); } } } else { pair<int,pair<int,int>>xd={kolor[lst], {ind1[{p, kolor[lst]}], -1}}; auto it=lower_bound(all(V[p]), xd); int x=it-V[p].begin(); if(!odw[{V[p][x].nd.nd, -1}]) { q.push({-o-sum[{p, kolor[lst]}]+koszt[lst]+ma1[{p, kolor[lst]}], {V[p][x].nd.nd, -1}}); } } } cout << (odl[n-1]==INF?-1:odl[n-1]) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...