Submission #1193169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193169		meisgood	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	1095 ms	10960 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long
int cost[100003] ;
int aa[100003],bb[100003],dd[100003] ;
set <int> adj[203] ;
set <int> adj2[203] ;
int used[100003] ;
int n,m ;
bool ok=0 ;
void con(int xx){
  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] ;
        used[id]=1 ;
        if (id-m>=0) used[id-m]=1 ;
      }
    }
  }
  if (vis[n]) ok=1 ;
}
int dij(int xx){
  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() ;
    // cout << x << endl ;
    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] ;
      }
    }
  }
  // cout << xx << endl ; cout << endl ;
  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) ;
    aa[i+m]=bb[i],bb[i+m]=aa[i],dd[i+m]=dd[i],cost[i+m]=cost[i] ;
    adj2[aa[i]].insert(i) ;
    adj2[bb[i]].insert(i+m) ;
  }
  con(1) ;
  int tt=0 ;
  tt+=dij(1) ;
  tt+=dij(n) ;
  int mn=tt ;
  for (i = 0 ; i < m ; i ++){
    if (!ok||used[i]){
      // cout << i ;
      int tt=0 ;
      adj[aa[i]].erase(i) ;
      swap(aa[i],bb[i]) ;
      adj[aa[i]].insert(i) ;
      tt+=dij(1) ;
      tt+=dij(n) ;
      // cout << i << " " << tt << endl ;
      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]) ;
    }
  }
  if (mn>=LLONG_MAX/4){
    cout << -1 << endl ;
    return 0 ;
  }
  cout << mn << endl ;
  return 0;
}

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