제출 #703630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
703630		EthanKim8683	Robot (JOI21_ho_t4)	C++17	24 / 100	1789 ms	132224 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=100000;
const Lli MAX=1e18;
map<pair<I,I>,map<pair<I,I>,Lli>>adjs;
map<I,Lli>tots[N];
priority_queue<tuple<Lli,pair<I,I>,I,Lli>>ques;
map<pair<I,I>,Lli>diss;
void add(Lli dis,I a,I c,I p,Lli pre){
  if(!diss.count({a,c}))diss[{a,c}]=MAX;
  if(dis>=diss[{a,c}])return;
  ques.push({-(diss[{a,c}]=dis),{a,c},p,pre});
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I n,m;cin>>n>>m;
  for(I i=0;i<m;i++){
    I a,b,c,p;cin>>a>>b>>c>>p,a--,b--,c--;
    adjs[{a,c}][{b,c}]=adjs[{b,c}][{a,c}]=p;
    adjs[{a,m}][{b,c}]=adjs[{b,m}][{a,c}]=p;
    tots[a][c]+=p,tots[b][c]+=p;
  }
  add(0,0,m,-1,0);
  while(ques.size()){
    auto[dis,stt1,par,pre]=ques.top();ques.pop();
    if((dis=-dis)!=diss[stt1])continue;
    for(auto[stt2,p]:adjs[stt1]){
      auto[a,c1]=stt1;auto[b,c2]=stt2;
      if(b==par)continue;
      p=min(p,tots[a][c2]-p-(c1==c2)*pre);
      add(dis+p,b,c2,a,p),add(dis+p,b,m,a,p);
    }
  }
  printf("%lli\n",diss.count({n-1,m})?diss[{n-1,m}]:-1);
}

• Subtask 1: 0 / 34
• Subtask 2: 24 / 24
• Subtask 3: 0 / 42