Submission #207084

#	Time	Username	Problem	Language	Result	Execution time	Memory
207084		Saboon	Olympic Bus (JOI20_ho_t4)	C++14	37 / 100	1045 ms	12848 KiB

ho_t4

// In the name of Allah 
// There is no power but from God the Almighty 
// No God except Allah 
#include <bits/stdc++.h> 
#define mp make_pair 
#define f1 first 
#define f2 second 
#define pb push_back 
#define pii pair<int ,int> 
#define ios  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
using namespace std; 
const int mox=2e2+9; 
vector<pair< pair<int , long long > ,int > > v[mox][2]; 
bool ok[50009]; 
set<pii> s; 
long long d[mox][17*mox]; 
int dad[mox][17*mox]; 
long long po[50009]; 
vector<pair<pii , int > > g; 
int n,m; 
void dj(int o,int y ,int no,int q) 
{ 
      s.insert({0,y}); 
     for(int i=1 ; i<=n ; i++) 
      d[i][o]=1e10; 
     d[y][o]=0; 
     while(s.empty()==0) 
     { 
         int x=s.begin()->f2; 
         s.erase(s.begin()); 
         for(pair<pii,int> i:v[x][q]) 
         { 
             if(d[i.f1.f1][o]>d[x][o]+i.f1.f2&&i.f2!=no) 
             { 
                 s.erase({d[i.f1.f1][o],i.f1.f1}); 
                 d[i.f1.f1][o]=d[x][o]+i.f1.f2; 
                 s.insert({d[i.f1.f1][o],i.f1.f1}); 
               dad[i.f1.f1][o]=i.f2; 
             } 
         } 
     } 
} 
 main() 
 {  ios 
int subbbb; 
     cin>>n>>m; 
     for(int i=0 ; i<m ; i++) 
     { 
         int a,b,c,e; 
         cin>>a>>b>>c>>e; 
         v[a][0].pb({{b,c},i}); 
         v[b][1].pb({{a,c},i}); 
         po[i]=e; 
         g.pb({{a,b},c}); 
     } 
     dj(0,1,-1,0); 
     dj(1,n,-1,0); 
     dj(2,1,-1,1); 
     dj(3,n,-1,1); 
         for(int j=1 ; j<=n ; j++) 
         { 
             ok[dad[j][0]]=1; 
             ok[dad[j][1]]=1; 
             ok[dad[j][2]]=1; 
             ok[dad[j][3]]=1; 
         } 
     long long ans=d[1][1]+d[n][0]; 
     int w=4; 
     for(int i=0 ; i<m ; i++) 
     { 
       if(ok[i]==1) 
       { 
        dj(w,1,i,0); 
        w++; 
        dj(w,n,i,0); 
        w++; 
        dj(w,1,i,1); 
        w++; 
        dj(w,n,i,1); 
        w++; 
       long long x=d[g[i].f1.f2][w-4]+d[g[i].f1.f1][w-1]+g[i].f2; 
       long long y=d[g[i].f1.f2][w-3]+d[g[i].f1.f1][w-2]+g[i].f2; 
       long long p=(x+y+po[i]); 
           ans=min(ans,p); 
          ans=min(x+d[1][w-3]+po[i],ans); 
          ans=min(y+d[n][w-4]+po[i],ans); 
 
       } 
       else
       { 
       long long x=d[g[i].f1.f2][0]+d[g[i].f1.f1][3]+g[i].f2; 
       long long  y=d[g[i].f1.f2][1]+d[g[i].f1.f1][2]+g[i].f2; 
       long long p=(x+y+po[i]); 
        ans=min(ans,p); 
        ans=min(x+d[1][1]+po[i],ans); 
        ans=min(y+d[n][0]+po[i],ans); 
       } 
 
     } 
     if(ans<1e10) 
     cout<<ans; 
     else
        cout<<-1; 
 } 

Compilation message (stderr)

ho_t4.cpp:43:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  main() 
       ^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:45:5: warning: unused variable 'subbbb' [-Wunused-variable]
 int subbbb; 
     ^~~~~~

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