제출 #1193160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193160		meisgood	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	1095 ms	4728 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long
int cost[50003] ;
int aa[50003],bb[50003],dd[50003] ;
set <int> adj[203] ;
int used[50003] ;
int n,m ;
int dij(int xx,int aaa){
  priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q ;
  vector <int> vis(203,0) ;
  vector <int> dist(203,LLONG_MAX/4) ;
  q.push({0,xx}) ;
  dist[xx]=0 ;
  while (!q.empty()){
    auto [d,x]=q.top() ;
    q.pop() ;
    if (vis[x]) continue ;
    vis[x]=1 ;
    for (auto id : adj[x]){
      if (dist[bb[id]]>d+dd[id]){
        q.push({d+dd[id],bb[id]}) ;
        dist[bb[id]]=d+dd[id] ;
        if (aaa==1) used[id]=1 ;
      }
    }
  }
  if (xx==1) return dist[n] ;
  else return dist[1] ;
}
signed main() {
  int i,j ;
  cin >> n >> m ;
  for (i = 0 ; i < m ; i ++){
    cin >> aa[i] >> bb[i] >> dd[i] >> cost[i] ;
    adj[aa[i]].insert(i) ;
  }
  int tt=0 ;
  tt+=dij(1,1) ;
  tt+=dij(n,1) ;
  if (tt>=LLONG_MAX/4){
    cout << -1 << endl ;
    return 0 ;
  }
  int mn=tt ;
  for (i = 0 ; i < m ; i ++){
    if (used[i]){
      int tt=0 ;
      adj[aa[i]].erase(i) ;
      swap(aa[i],bb[i]) ;
      adj[aa[i]].insert(i) ;
      tt+=dij(1,0) ;
      tt+=dij(n,0) ;
      adj[aa[i]].erase(i) ;
      swap(aa[i],bb[i]) ;
      adj[aa[i]].insert(i) ;
      mn=min(mn,tt+cost[i]) ;
    }
    else {
      mn=min(mn,tt+cost[i]) ;
    }
  }
  cout << mn << endl ;
  return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63