Submission #920158

#	Time	Username	Problem	Language	Result	Execution time	Memory
920158		vjudge1	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	446 ms	6632 KiB

ho_t4

    #include "bits/stdc++.h"
    #pragma optimize ("Bismillahirrahmanirrahim")
    using namespace std;
    #define pb push_back
    #define ff first
    #define ss second
    #define endl "\n" 
    #define int long long
    #define double long double
    #define sz(x) ((int)(x).size())
    #define all(x) (x).begin(), (x).end()
    #define rall(x) (x).rbegin(), (x).rend()
    #define what_is(x) cerr << #x << " is " << x << endl;
    //#define m (l+r)/2
    constexpr int N=200005;
    constexpr int MOD=1000000007;
    constexpr int  INF2 = LLONG_MAX;
    constexpr int INF=(int)1e15;
    constexpr int LOG=30;
    typedef pair<int,int> pii;
    typedef tuple<int,int,int> tp;
    typedef priority_queue<pii,vector<pii>,greater<pii>> min_pq;
    typedef priority_queue<pii> max_pq;
    typedef long long ll;
    //to think//
    /*
     * graph approach
     * dp
     * dividing the problem to smaller statements
     * finding the real constraint
     * sqrt decomposition
     * greedy approach
     * pigeonhole principle
     * rewriting the problem/equality 
     * bitwise approaches
     * binary search if monotonic
     * divide and conquer
     * combinatorics
     * inclusion - exclusion
     * think like bfs
    */
     
     
     
    inline int in()
    {
      int x;cin >> x;
      return x;
    }
     
    inline string in2()
    {
      string x;cin >> x;
      return x;
    }
     
    /*
     1- sp route cikar (n^2 dijkstra ile)
     2- sp routetaki her edge için tekrardan dijkstra(n^2) at
     3- sp routetaki edge değilse dist[1][b] + c + d dist[a][n] dene
    */
     
    int n,m;
     
    multiset<array<int,4>> git;
    vector<array<int,4>> edge;
     
    multiset<array<int,3>> v[205];
     
    int dijk(int rt)
    {
      int di[n+2];
      bool vis[n+2];
     
      for(int i=1;i<=n;i++) {di[i]=INF;vis[i]=0;}
     
      di[rt]=0;
     
      for(int i=1;i<=n;i++)
      {
        pii cur={INF,INF};
        for(int j=1;j<=n;j++) if(vis[j]==0) cur=min(cur,{di[j],j});
        if(cur.ff==INF) break;
        vis[cur.ss]=1;
        for(array<int,3> x:v[cur.ss]) if(cur.ff+x[1]<di[x[0]]) di[x[0]]=cur.ff+x[1];
      }
      
      if(rt==1) return di[n];
      else return di[1];
    }
     
    void rout(int rt)
    {
      int di[n+1];
      bool vis[n+1];
      for(int i=1;i<=n;i++) {di[i]=INF;vis[i]=0;}
      di[rt]=0;
      
      array<int,3> par[n+1];
     
      for(int i=1;i<=n;i++)
      {
        pii cur={INF,INF};
        for(int j=1;j<=n;j++) if(vis[j]==0) cur=min(cur,{di[j],j});
        if(cur.ff==INF) break;
        vis[cur.ss]=1;
        for(array<int,3> x:v[cur.ss]) 
          if(cur.ff+x[1]<di[x[0]]) 
            {par[x[0]]={cur.ss,x[1],x[2]};di[x[0]]=cur.ff+x[1];}
      }
      
     
      if(rt==1)
      {
        if(vis[n]==0) return;
        int xd=n;
        while(xd!=1)
        {
          git.insert({par[xd][0],xd,par[xd][1],par[xd][2]});
          xd=par[xd][0];
        }
      }
      else
      {
        int xd=1;
        if(vis[1]==0) return;
        while(xd!=n)
        {
          git.insert({par[xd][0],xd,par[xd][1],par[xd][2]});
          xd=par[xd][0];
        }
      }
    }
     
     
    int dist[202][202];
     
    void solve()
    {
      n=in(),m=in();
      for(int i=1;i<=201;i++) for(int j=1;j<=201;j++) dist[i][j]=INF;
      for(int i=1;i<=201;i++) dist[i][i]=0;
      
      for(int i=1;i<=m;i++)
      {
        int a=in(),b=in(),c=in(),d=in();
        edge.pb({a,b,c,d});
        dist[a][b]=min(dist[a][b],c);
        v[a].insert({b,c,d});
      }
      
      rout(1);
      rout(n);
     
      for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
          for(int j=1;j<=n;j++)
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
      
       
      int ans=dist[1][n]+dist[n][1];
      for(array<int,4> x:edge)
      {
        int gitme=INF;
        int gelme=INF;
        if(git.count(x)==1)
        { 
          v[x[0]].erase(v[x[0]].find({x[1],x[2],x[3]}));
          v[x[1]].insert({x[0],x[2],x[3]});
          gitme=min(gitme,dijk(1));
          gelme=min(gelme,dijk(n));
          v[x[1]].erase(v[x[1]].find({x[0],x[2],x[3]}));
          v[x[0]].insert({x[1],x[2],x[3]});
          ans=min(ans,gitme+gelme+x[3]);
        }
        else
        {
          gitme=min(gitme,dist[1][n]);
          gitme=min(gitme,dist[1][x[1]]+dist[x[0]][n]+x[2]);
          gelme=min(gelme,dist[n][1]);
          gelme=min(gelme,dist[n][x[1]]+x[2]+dist[x[0]][1]);
          ans=min(ans,gitme+gelme+x[3]);
        }
      }
     
      cout << (ans>=INF ? -1 :ans) << endl;
    }
     
    int32_t main(){
       
     
      cin.tie(0); ios::sync_with_stdio(0);
      cout << fixed <<  setprecision(15);
       
      int t=1;//t=in();
     
       for(int i=1;i<=t;i++)
       {
         //cout << "Case #" << i << ": ";
         solve();
       }
     
     return 0;
    }

Compilation message (stderr)

ho_t4.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 |     #pragma optimize ("Bismillahirrahmanirrahim")
      |

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