Submission #922822

#	Time	Username	Problem	Language	Result	Execution time	Memory
922822		vjudge1	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1088 ms	15536 KiB

ho_t4

// Отче наш, сущий на небесах! Да святится имя Твое; да приидет Царствие Твое; да будет воля Твоя и на земле, как на небе; хлеб наш насущный подавай нам на каждый день; и прости нам грехи наши, ибо и мы прощаем всякому должнику нашему; и не введи нас в искушение, но избавь нас от лукавого ML, TL, WA
#include <bits/stdc++.h>

#pragma optimize("Ofast")
#pragma target("avx2")

#define ll long long
#define ld long double
#define pii pair<int,int>
#define F first
#define S second
#define in insert
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz(s) (int)s.size()
#define ppb pop_back
#define mem(a,i) memset(a,i,sizeof(a))
#define lb lower_bound
#define ub upper_bound
#define int ll

using namespace std;

const int MAX=2e5+10;
const int N=1000+10;
const int inf=1e18;
const int mod=1e9+9;
const int B=2003;
const ld eps=1e-9;

const int dx[4]={0,0,1,-1};
const int dy[4]={-1,1,0,0};

int binpow(int a,int n){
  if(n==0)return 1;
  if(n%2==1)return a*binpow(a,n-1)%mod;
  int k=binpow(a,n/2);
  return (k*k)%mod;
}

int n,m;
int a[MAX],b[MAX],c[MAX],dd[MAX];
vector<pii> g[MAX];
int d[MAX],d1[MAX];

int calc(int reb){
  for(int i=1;i<=n;i++){
    g[i].clear();
    d[i]=inf;
    d1[i]=inf;
  }
  for(int i=1;i<=m;i++){
    if(i==reb){
      g[b[i]].pb({a[i],c[i]});
    }
    else{
      g[a[i]].pb({b[i],c[i]});
    }
  }
  d[1]=0;
  priority_queue<pii> q;
  q.push({0,1});
  while(!q.empty()){
    int v=q.top().S;
    int w=q.top().F;
    q.pop();
    if(w+d[v]!=0)continue;
    for(auto to:g[v]){
      if(d[to.F]>d[v]+to.S){
        d[to.F]=d[v]+to.S;
        q.push({-d[to.F],to.F});
      }
    }
  }
  d1[n]=0;
  q.push({0,n});
  while(!q.empty()){
    int v=q.top().S;
    int w=q.top().F;
    q.pop();
    if(w+d1[v]!=0)continue;
    for(auto to:g[v]){
      if(d1[to.F]>d1[v]+to.S){
        d1[to.F]=d1[v]+to.S;
        q.push({-d1[to.F],to.F});
      }
    }
  }  
  return d[n]+d1[1];
}

void solve(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    cin>>a[i]>>b[i]>>c[i]>>dd[i];
  }
  int ans=inf;
  for(int i=0;i<=m;i++){
    ans=min(ans,calc(i)+dd[i]);
    // cout<<i<<" "<<calc(i)<<"\n";
  }
  if(ans==inf)cout<<-1;
  else cout<<ans;
}

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  // cin>>t;
  while(t--){
    solve();
  }
}

Compilation message (stderr)

ho_t4.cpp:4: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    4 | #pragma optimize("Ofast")
      | 
ho_t4.cpp:5: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    5 | #pragma target("avx2")
      |

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