Submission #699608

#	Time	Username	Problem	Language	Result	Execution time	Memory
699608		amin	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	1740 ms	45264 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define rep(a,b) for(int i=a;i<b;i++)
vector<ll>v[200000],co[200000];
ll solve(int n,int a,int b,int c,int d)
{
    int vis[n];
    ll val[n],val2[n],mval[n],val3[n],mval2[n],val4[n];
    rep(0,n)
    {
        val3[i]=1e18;
        val4[i]=1e18;
        mval2[i]=1e18;
        vis[i]=0;
        val[i]=0;
        mval[i]=1e18;

    }
    priority_queue<pair<ll,ll> >q;
    q.push({0,c});
    //cout<<1<<endl;
    while(!q.empty())
    {
        ll sum=-q.top().first;
       ll in=q.top().second;
        q.pop();
        if(vis[in])
            continue;
        vis[in]=1;
        val[in]=sum;
        for(int i=0;i<v[in].size();i++)
        {

            q.push({-sum-co[in][i],v[in][i]});
        }
    }

    for(int i=0;i<n;i++)
    {
        vis[i]=0;
    }
     q.push({0,d});
    // cout<<2<<endl;
    while(!q.empty())
    {

        ll sum=-q.top().first;
        ll in=q.top().second;
        q.pop();
        if(vis[in])
            continue;
        vis[in]=1;
        val2[in]=sum;
        for(int i=0;i<v[in].size();i++)
        {

            q.push({-sum-co[in][i],v[in][i]});
        }
    }
    rep(0,n)
    vis[i]=0;
    priority_queue<pair<ll,pair<ll,ll> > >pq;
    pq.push({0,{-val[a],a}});
   // cout<<3<<endl;
    val3[a]=0;
    while(!pq.empty())
    {
        ll sum=-pq.top().first;

        ll mi=-pq.top().second.first;
        int in=pq.top().second.second;
        pq.pop();

    //    cout<<pq.size()<<' '<<vis[in]<<endl;
        if(vis[in]==1)
            continue;
            mval[in]=mi;
        vis[in]=1;
        //pq.pop();
        rep(0,v[in].size())
        {
            int k=v[in][i];
            ll newval=sum+co[in][i];
            if(newval<val3[k])
            {
                val3[k]=newval;
                mval[k]=min(mval[in],val[k]);
                pq.push({-newval,{-mval[k],k}});
            }
            if(newval==val3[k])
            {
                mval[k]=min(mval[k],mval[in]);
                pq.push({-newval,{-mval[k],k}});

            }
        }

    }
    rep(0,n)
    vis[i]=0;
    val4[b]=0;
    pq.push({0,{-val2[b],b}});
     while(!pq.empty())
    {
        ll sum=-pq.top().first;

        ll mi=-pq.top().second.first;
        int in=pq.top().second.second;
        pq.pop();

    //    cout<<pq.size()<<' '<<vis[in]<<endl;
        if(vis[in]==1)
            continue;
            mval2[in]=mi;
        vis[in]=1;
        //pq.pop();
        rep(0,v[in].size())
        {
            int k=v[in][i];
            ll newval=sum+co[in][i];
            if(newval<val4[k])
            {
                val4[k]=newval;
                mval2[k]=min(mval2[in],val2[k]);
                pq.push({-newval,{-mval2[k],k}});
            }
            if(newval==val4[k])
            {
                mval2[k]=min(mval2[k],mval2[in]);
                pq.push({-newval,{-mval2[k],k}});

            }
        }

    }
    ll ans=1e18;
    for(int i=0;i<n;i++)
    {
        //cout<<val3[i]<<' '<<val4[i]<<endl;
        if(val3[i]+val4[i]==val3[b])
        {
          //  cout<<i<<' '<<mval[i]<<' '<<mval2[i]<<endl;
            ans=min(ans,mval[i]+mval2[i]);
        }
    }

    ans=min(ans,val[d]);
    return ans;

    }








int main()
{
    int n;
    cin>>n;
    int m;
    cin>>m;
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    a--;
    b--;
    c--;
    d--;
   // for(int i=0
          rep(0,m)
          {
int x,y,z;
cin>>x>>y>>z;
x--;
y--;
v[x].push_back(y);
v[y].push_back(x);
co[x].push_back(z);
co[y].push_back(z);

          }
          ll ans=1e18;
          ans=min(ans, solve(n,a,b,c,d));
         ans=min(ans, solve(n,a,b,c,d));
           ans=min(ans, solve(n,b,a,c,d));
         ans=min(ans, solve(n,b,a,d,c));
         cout<<ans;

}

Compilation message (stderr)

commuter_pass.cpp: In function 'long long int solve(int, int, int, int, int)':
commuter_pass.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int i=0;i<v[in].size();i++)
      |                     ~^~~~~~~~~~~~~
commuter_pass.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int i=0;i<v[in].size();i++)
      |                     ~^~~~~~~~~~~~~
commuter_pass.cpp:77:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   77 |         if(vis[in]==1)
      |         ^~
commuter_pass.cpp:79:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   79 |             mval[in]=mi;
      |             ^~~~
commuter_pass.cpp:5:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a,b) for(int i=a;i<b;i++)
      |                              ~^~~~~~~
    6 | vector<ll>v[200000],co[200000];
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    7 | ll solve(int n,int a,int b,int c,int d)
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    8 | {
      | ~                              
    9 |     int vis[n];
      |     ~~~~~~~~~~~                
   10 |     ll val[n],val2[n],mval[n],val3[n],mval2[n],val4[n];
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   11 |     rep(0,n)
      |     ~~~~~~~~                   
   12 |     {
      |     ~                          
   13 |         val3[i]=1e18;
      |         ~~~~~~~~~~~~~          
   14 |         val4[i]=1e18;
      |         ~~~~~~~~~~~~~          
   15 |         mval2[i]=1e18;
      |         ~~~~~~~~~~~~~~         
   16 |         vis[i]=0;
      |         ~~~~~~~~~              
   17 |         val[i]=0;
      |         ~~~~~~~~~              
   18 |         mval[i]=1e18;
      |         ~~~~~~~~~~~~~          
   19 | 
      |                                
   20 |     }
      |     ~                          
   21 |     priority_queue<pair<ll,ll> >q;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   22 |     q.push({0,c});
      |     ~~~~~~~~~~~~~~             
   23 |     //cout<<1<<endl;
      |     ~~~~~~~~~~~~~~~~           
   24 |     while(!q.empty())
      |     ~~~~~~~~~~~~~~~~~          
   25 |     {
      |     ~                          
   26 |         ll sum=-q.top().first;
      |         ~~~~~~~~~~~~~~~~~~~~~~ 
   27 |        ll in=q.top().second;
      |        ~~~~~~~~~~~~~~~~~~~~~   
   28 |         q.pop();
      |         ~~~~~~~~               
   29 |         if(vis[in])
      |         ~~~~~~~~~~~            
   30 |             continue;
      |             ~~~~~~~~~          
   31 |         vis[in]=1;
      |         ~~~~~~~~~~             
   32 |         val[in]=sum;
      |         ~~~~~~~~~~~~           
   33 |         for(int i=0;i<v[in].size();i++)
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   34 |         {
      |         ~                      
   35 | 
      |                                
   36 |             q.push({-sum-co[in][i],v[in][i]});
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   37 |         }
      |         ~                      
   38 |     }
      |     ~                          
   39 | 
      |                                
   40 |     for(int i=0;i<n;i++)
      |     ~~~~~~~~~~~~~~~~~~~~       
   41 |     {
      |     ~                          
   42 |         vis[i]=0;
      |         ~~~~~~~~~              
   43 |     }
      |     ~                          
   44 |      q.push({0,d});
      |      ~~~~~~~~~~~~~~            
   45 |     // cout<<2<<endl;
      |     ~~~~~~~~~~~~~~~~~          
   46 |     while(!q.empty())
      |     ~~~~~~~~~~~~~~~~~          
   47 |     {
      |     ~                          
   48 | 
      |                                
   49 |         ll sum=-q.top().first;
      |         ~~~~~~~~~~~~~~~~~~~~~~ 
   50 |         ll in=q.top().second;
      |         ~~~~~~~~~~~~~~~~~~~~~  
   51 |         q.pop();
      |         ~~~~~~~~               
   52 |         if(vis[in])
      |         ~~~~~~~~~~~            
   53 |             continue;
      |             ~~~~~~~~~          
   54 |         vis[in]=1;
      |         ~~~~~~~~~~             
   55 |         val2[in]=sum;
      |         ~~~~~~~~~~~~~          
   56 |         for(int i=0;i<v[in].size();i++)
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   57 |         {
      |         ~                      
   58 | 
      |                                
   59 |             q.push({-sum-co[in][i],v[in][i]});
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   60 |         }
      |         ~                      
   61 |     }
      |     ~                          
   62 |     rep(0,n)
      |     ~~~~~~~~                   
   63 |     vis[i]=0;
      |     ~~~~~~~~~                  
   64 |     priority_queue<pair<ll,pair<ll,ll> > >pq;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   65 |     pq.push({0,{-val[a],a}});
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~  
   66 |    // cout<<3<<endl;
      |    ~~~~~~~~~~~~~~~~~           
   67 |     val3[a]=0;
      |     ~~~~~~~~~~                 
   68 |     while(!pq.empty())
      |     ~~~~~~~~~~~~~~~~~~         
   69 |     {
      |     ~                          
   70 |         ll sum=-pq.top().first;
      |         ~~~~~~~~~~~~~~~~~~~~~~~
   71 | 
      |                                
   72 |         ll mi=-pq.top().second.first;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   73 |         int in=pq.top().second.second;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   74 |         pq.pop();
      |         ~~~~~~~~~              
   75 | 
      |                                
   76 |     //    cout<<pq.size()<<' '<<vis[in]<<endl;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   77 |         if(vis[in]==1)
      |         ~~~~~~~~~~~~~~         
   78 |             continue;
      |             ~~~~~~~~~          
   79 |             mval[in]=mi;
      |             ~~~~~~~~~~~~       
   80 |         vis[in]=1;
      |         ~~~~~~~~~~             
   81 |         //pq.pop();
      |         ~~~~~~~~~~~            
   82 |         rep(0,v[in].size())
      |         ~~~~~~~~~~~~~~~~~~     
commuter_pass.cpp:82:9: note: in expansion of macro 'rep'
   82 |         rep(0,v[in].size())
      |         ^~~
commuter_pass.cpp:114:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  114 |         if(vis[in]==1)
      |         ^~
commuter_pass.cpp:116:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  116 |             mval2[in]=mi;
      |             ^~~~~
commuter_pass.cpp:5:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a,b) for(int i=a;i<b;i++)
      |                              ~^~~~~~~
    6 | vector<ll>v[200000],co[200000];
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    7 | ll solve(int n,int a,int b,int c,int d)
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    8 | {
      | ~                              
    9 |     int vis[n];
      |     ~~~~~~~~~~~                
   10 |     ll val[n],val2[n],mval[n],val3[n],mval2[n],val4[n];
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   11 |     rep(0,n)
      |     ~~~~~~~~                   
   12 |     {
      |     ~                          
   13 |         val3[i]=1e18;
      |         ~~~~~~~~~~~~~          
   14 |         val4[i]=1e18;
      |         ~~~~~~~~~~~~~          
   15 |         mval2[i]=1e18;
      |         ~~~~~~~~~~~~~~         
   16 |         vis[i]=0;
      |         ~~~~~~~~~              
   17 |         val[i]=0;
      |         ~~~~~~~~~              
   18 |         mval[i]=1e18;
      |         ~~~~~~~~~~~~~          
   19 | 
      |                                
   20 |     }
      |     ~                          
   21 |     priority_queue<pair<ll,ll> >q;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   22 |     q.push({0,c});
      |     ~~~~~~~~~~~~~~             
   23 |     //cout<<1<<endl;
      |     ~~~~~~~~~~~~~~~~           
   24 |     while(!q.empty())
      |     ~~~~~~~~~~~~~~~~~          
   25 |     {
      |     ~                          
   26 |         ll sum=-q.top().first;
      |         ~~~~~~~~~~~~~~~~~~~~~~ 
   27 |        ll in=q.top().second;
      |        ~~~~~~~~~~~~~~~~~~~~~   
   28 |         q.pop();
      |         ~~~~~~~~               
   29 |         if(vis[in])
      |         ~~~~~~~~~~~            
   30 |             continue;
      |             ~~~~~~~~~          
   31 |         vis[in]=1;
      |         ~~~~~~~~~~             
   32 |         val[in]=sum;
      |         ~~~~~~~~~~~~           
   33 |         for(int i=0;i<v[in].size();i++)
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   34 |         {
      |         ~                      
   35 | 
      |                                
   36 |             q.push({-sum-co[in][i],v[in][i]});
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   37 |         }
      |         ~                      
   38 |     }
      |     ~                          
   39 | 
      |                                
   40 |     for(int i=0;i<n;i++)
      |     ~~~~~~~~~~~~~~~~~~~~       
   41 |     {
      |     ~                          
   42 |         vis[i]=0;
      |         ~~~~~~~~~              
   43 |     }
      |     ~                          
   44 |      q.push({0,d});
      |      ~~~~~~~~~~~~~~            
   45 |     // cout<<2<<endl;
      |     ~~~~~~~~~~~~~~~~~          
   46 |     while(!q.empty())
      |     ~~~~~~~~~~~~~~~~~          
   47 |     {
      |     ~                          
   48 | 
      |                                
   49 |         ll sum=-q.top().first;
      |         ~~~~~~~~~~~~~~~~~~~~~~ 
   50 |         ll in=q.top().second;
      |         ~~~~~~~~~~~~~~~~~~~~~  
   51 |         q.pop();
      |         ~~~~~~~~               
   52 |         if(vis[in])
      |         ~~~~~~~~~~~            
   53 |             continue;
      |             ~~~~~~~~~          
   54 |         vis[in]=1;
      |         ~~~~~~~~~~             
   55 |         val2[in]=sum;
      |         ~~~~~~~~~~~~~          
   56 |         for(int i=0;i<v[in].size();i++)
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   57 |         {
      |         ~                      
   58 | 
      |                                
   59 |             q.push({-sum-co[in][i],v[in][i]});
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   60 |         }
      |         ~                      
   61 |     }
      |     ~                          
   62 |     rep(0,n)
      |     ~~~~~~~~                   
   63 |     vis[i]=0;
      |     ~~~~~~~~~                  
   64 |     priority_queue<pair<ll,pair<ll,ll> > >pq;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   65 |     pq.push({0,{-val[a],a}});
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~  
   66 |    // cout<<3<<endl;
      |    ~~~~~~~~~~~~~~~~~           
   67 |     val3[a]=0;
      |     ~~~~~~~~~~                 
   68 |     while(!pq.empty())
      |     ~~~~~~~~~~~~~~~~~~         
   69 |     {
      |     ~                          
   70 |         ll sum=-pq.top().first;
      |         ~~~~~~~~~~~~~~~~~~~~~~~
   71 | 
      |                                
   72 |         ll mi=-pq.top().second.first;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   73 |         int in=pq.top().second.second;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   74 |         pq.pop();
      |         ~~~~~~~~~              
   75 | 
      |                                
   76 |     //    cout<<pq.size()<<' '<<vis[in]<<endl;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   77 |         if(vis[in]==1)
      |         ~~~~~~~~~~~~~~         
   78 |             continue;
      |             ~~~~~~~~~          
   79 |             mval[in]=mi;
      |             ~~~~~~~~~~~~       
   80 |         vis[in]=1;
      |         ~~~~~~~~~~             
   81 |         //pq.pop();
      |         ~~~~~~~~~~~            
   82 |         rep(0,v[in].size())
      |         ~~~~~~~~~~~~~~~~~~~    
   83 |         {
      |         ~                      
   84 |             int k=v[in][i];
      |             ~~~~~~~~~~~~~~~    
   85 |             ll newval=sum+co[in][i];
      |             ~~~~~~~~~~~~~~~~~~~~~~~~
   86 |             if(newval<val3[k])
      |             ~~~~~~~~~~~~~~~~~~ 
   87 |             {
      |             ~                  
   88 |                 val3[k]=newval;
      |                 ~~~~~~~~~~~~~~~
   89 |                 mval[k]=min(mval[in],val[k]);
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   90 |                 pq.push({-newval,{-mval[k],k}});
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   91 |             }
      |             ~                  
   92 |             if(newval==val3[k])
      |             ~~~~~~~~~~~~~~~~~~~
   93 |             {
      |             ~                  
   94 |                 mval[k]=min(mval[k],mval[in]);
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   95 |                 pq.push({-newval,{-mval[k],k}});
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   96 | 
      |                                
   97 |             }
      |             ~                  
   98 |         }
      |         ~                      
   99 | 
      |                                
  100 |     }
      |     ~                          
  101 |     rep(0,n)
      |     ~~~~~~~~                   
  102 |     vis[i]=0;
      |     ~~~~~~~~~                  
  103 |     val4[b]=0;
      |     ~~~~~~~~~~                 
  104 |     pq.push({0,{-val2[b],b}});
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~ 
  105 |      while(!pq.empty())
      |      ~~~~~~~~~~~~~~~~~~        
  106 |     {
      |     ~                          
  107 |         ll sum=-pq.top().first;
      |         ~~~~~~~~~~~~~~~~~~~~~~~
  108 | 
      |                                
  109 |         ll mi=-pq.top().second.first;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  110 |         int in=pq.top().second.second;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  111 |         pq.pop();
      |         ~~~~~~~~~              
  112 | 
      |                                
  113 |     //    cout<<pq.size()<<' '<<vis[in]<<endl;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  114 |         if(vis[in]==1)
      |         ~~~~~~~~~~~~~~         
  115 |             continue;
      |             ~~~~~~~~~          
  116 |             mval2[in]=mi;
      |             ~~~~~~~~~~~~~      
  117 |         vis[in]=1;
      |         ~~~~~~~~~~             
  118 |         //pq.pop();
      |         ~~~~~~~~~~~            
  119 |         rep(0,v[in].size())
      |         ~~~~~~~~~~~~~~~~~~     
commuter_pass.cpp:119:9: note: in expansion of macro 'rep'
  119 |         rep(0,v[in].size())
      |         ^~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45