제출 #768823

#제출 시각아이디문제언어결과실행 시간메모리
768823LeoChen112358Robot (JOI21_ho_t4)C++14
34 / 100
3121 ms1079580 KiB
#include <bits/stdc++.h> using namespace std; const int Nlim=1e5,Mlim=2e5,Vlim=1e9; const long INF=(long)Vlim*Mlim+1; #define pii pair<long,pair<int,int>> int N,M; struct edge{ int node,color,price; edge(int nn,int cc,int pp){ node=nn; color=cc; price=pp; } }; map<int,vector<edge>>conn[Nlim]; //cost = min(recolor you, recolor neighbors) //cost to get to i long dp1[Nlim]; //cost to get to i with a c-edge and will go thru another c-edge (so we'll recolor later) //applies only when we are to recolor neighbors originally (gets affected) map<int,long>dp2[Nlim],sum[Nlim]; int main(){ cin>>N>>M; for(int i=0; i<M; i++){ int a,b,c,p; cin>>a>>b>>c>>p; a--,b--,c--; conn[a][c].push_back(edge(b,c,p)); conn[b][c].push_back(edge(a,c,p));//undirected sum[a][c]+=p; sum[b][c]+=p; } for(int i=0; i<N; i++){ dp1[i]=INF; for(int j=0; j<M; j++)dp2[i][j]=INF; } priority_queue<pii,vector<pii>,greater<pii>>PQ; PQ.push({0,{0,-1}});//cost,node,color dp1[0]=0; while(!PQ.empty()){ long prc=PQ.top().first,node=PQ.top().second.first,col=PQ.top().second.second; PQ.pop(); if(col==-1){//no need to recolor neighbor stuff (normal way) if(dp1[node]!=prc)continue; for(auto stuff:conn[node]){//each color for(auto i:stuff.second){ //1. recolor this edge long v1=prc+i.price; if(v1<dp1[i.node]){ dp1[i.node]=v1; PQ.push({dp1[i.node],{i.node,-1}}); } //2. recolor neighbors long v2=prc+sum[node][i.color]-i.price; if(v2<dp1[i.node]){ dp1[i.node]=v2; PQ.push({dp1[i.node],{i.node,-1}}); } //3. recolor at next step (virtual transition) if(dp2[i.node].count(i.color)==0 or prc<dp2[i.node][i.color]){ dp2[i.node][i.color]=prc; PQ.push({prc,{i.node,i.color}}); } } } } else{//need to recolor neighbor stuff (special case) if(dp2[node][col]!=prc)continue; for(auto i:conn[node][col]){ long val=sum[node][col]; if(prc+val-i.price<dp1[i.node]){ dp1[i.node]=prc+val-i.price; PQ.push({dp1[i.node],{i.node,-1}}); } } } } if(dp1[N-1]==INF)cout<<-1<<'\n'; else cout<<dp1[N-1]<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...