Submission #1226001

#TimeUsernameProblemLanguageResultExecution timeMemory
1226001boclobanchatRobot (JOI21_ho_t4)C++20
24 / 100
486 ms117088 KiB
#include<bits/stdc++.h> using namespace std; struct edge { int pos,id,val; }; bool comp(edge a,edge b) { return a.id<b.id; } const int MAXN=9e5+5; const long long INF=1e5; pair<int,int> val[MAXN]; vector<edge> ds[MAXN]; vector< pair<int,long long> > E[MAXN]; long long dp[MAXN]; int f(pair<int,int> a,int cnt) { return lower_bound(val+1,val+cnt+1,a)-val; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; for(int i=1;i<=m;i++) { int l,r,c,v; cin>>l>>r>>c>>v; ds[l].push_back({r,c,v}),ds[r].push_back({l,c,v}); val[i*2-1]={l,r},val[i*2]={r,l}; } sort(val+1,val+m*2+1); for(int i=1;i<=m*4;i++) E[i].push_back({m*4+val[(i-1)%(m*2)+1].second,0}); for(int i=1;i<=n;i++) { int sz=ds[i].size(),pre=0; sort(ds[i].begin(),ds[i].end(),comp); for(int j=1;j<=sz;j++) if(j==sz||ds[i][j].id!=ds[i][j-1].id) { long long sum=0; for(int k=pre;k<j;k++) sum+=ds[i][k].val; for(int k=pre;k<j;k++) E[m*4+i].push_back({f({i,ds[i][k].pos},m*2),sum-ds[i][k].val}); if(pre+2==j) { E[f({ds[i][j-2].pos,i},m*2)+m*2].push_back({f({i,ds[i][j-1].pos},m*2),0}); E[f({ds[i][j-1].pos,i},m*2)+m*2].push_back({f({i,ds[i][j-2].pos},m*2),0}); } pre=j; } for(auto v:ds[i]) { E[m*4+i].push_back({f({i,v.pos},m*2)+m*2,v.val}); // E[m*4+i].push_back({f({v.pos,i},m*2)+m*2,v.val}); } } for(int i=1;i<=m*4+n;i++) dp[i]=INF; priority_queue< pair<long long,int>,vector< pair<long long,int> >,greater< pair<long long,int> > > pq; pq.push({dp[m*4+1]=0,m*4+1}); while(!pq.empty()) { long long a=pq.top().first,b=pq.top().second; pq.pop(); if(dp[b]<a) continue; for(auto v:E[b]) if(dp[v.first]>a+v.second) pq.push({dp[v.first]=a+v.second,v.first}); } if(dp[m*4+n]==INF) return cout<<-1,0; cout<<dp[m*4+n]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...