Submission #555373

#	Time	Username	Problem	Language	Result	Execution time	Memory
555373		fadi57	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	354 ms	20192 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mx=1e5+9;
const ll inf=1e18;
ll dist[4][mx+9];
vector<pair<int,ll>>adj[mx];

int n,m,s,t,u,v;
ll dp[mx];
ll dp2[mx];
ll l;
 void dikjstra(int node,int cnt)
      {

    priority_queue<pair<ll,int>>q;

    for(int i=0; i<=n; i++)
    {
        dist[cnt][i]=inf;
    }
    q.push({0,node});
    // cout<<dist[0][2]<<endl;

    dist[cnt][node]=0;
    while(!q.empty())
    {
        pair<ll,int>me=q.top();
        q.pop();
        int x=me.second;

        ll cost=me.first;
        cost*=-1;
        // cout<<"TEST "<<x<<endl;
        for(auto it:adj[x])
        {
            int node2=it.first;
            //   cout<<it.first<<" "<<it.second<<endl;
            if(cost+it.second<dist[cnt][it.first])
            {
                //    cout<<node2<<"xx"<<endl;
                ll cost2=cost+it.second;
                dist[cnt][it.first]=cost2;
                q.push({(cost2)*-1,node2});

            }

        }

    }
 }


int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n>>m>>s>>t>>u>>v;
    for(int i=0; i<m; i++)
    {
        ll x,y,c;
        cin>>x>>y>>c;
        adj[x].push_back({y,c});
        adj[y].push_back({x,c});
    }
    dikjstra(s,0);
    dikjstra(t,1);
    dikjstra(u,2);
    dikjstra(v,3);
    l=dist[0][t];

    queue<pair<ll,int>>q;
    for(int i=1; i<=n; i++)
    {
        dp[i]=dp2[i]=inf;
    }
    int par[n+5];
    ll ans=inf;
    for(int i=1; i<=n; i++)
    {
        par[i]=-1;
    }
    q.push({0,s});

    int vis[n+5];
    memset(vis,0,sizeof(vis));
    while(!q.empty())
    {
        pair<ll,int >me=q.front();

        int x=me.second;
        vis[x]=1;
        ll cost=me.first;
        q.pop();
        //    cout<<x<<endl;
        dp[x]=min(dp[x],dist[3][x]);

        for(auto it:adj[x])
        {
            ll cost2=me.first+it.second;
            //    cout<<it.first<<" "<<cost2<<" "<<dist[0][it.first]<<endl;
            int z=it.first;
            if(l-(cost2)==dist[1][z]&&!vis[z]&&dist[0][z]+dist[1][z]==l)
            {
                par[z]=x;
                dp[it.first]=min(dp[it.first],dp[x]);
                q.push({cost2,it.first});
            }

        }
   // ans=min(ans,dp[x]+dist[2][x]);

    }

    q.push({0,t});
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=n; i++)
    {
        par[i]=-1;
    }
    while(!q.empty())
    {
        pair<ll,int >me=q.front();
        int x=me.second;
        vis[x]=1;
        ll cost=me.first;
        q.pop();
        //       cout<<x<<endl;
        dp2[x]=min(dp2[x],dist[3][x]);

        for(auto it:adj[x])
        {
            ll cost2=me.first+it.second;
            //    cout<<it.first<<" "<<cost2<<" "<<dist[0][it.first]<<endl;
            int z=it.first;
            if(l-(cost2)==dist[0][z]&&!vis[z]&&dist[0][z]+dist[1][z]==l)
            {
                par[it.first]=x;
                dp2[it.first]=min(dp2[it.first],dp2[x]);

                q.push({cost2,it.first});
            }

        }
    //ans=min(ans,dp2[x]+dist[2][x]);

    }


    for(int i=1; i<=n; i++)
    {
        if(dist[0][i]+dist[1][i]==l)
        {
            //    cout<<i<<" "<<endl;
            //  ans=min(dist[3][i],ans);
          ans=min(dist[2][i]+dp2[i],ans);
           ans=min(dist[2][i]+dp[i],ans);
            //  cout<<dist[2][i]<<" "<<dp[i]<<" "<<i<<endl;
        }
    }
    // cout<<dist[2][v]<<endl;

    //  cout<<dp2[1]<<endl;
    ans=min(ans,dist[2][v]);
    cout<<ans;

}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:93:12: warning: unused variable 'cost' [-Wunused-variable]
   93 |         ll cost=me.first;
      |            ^~~~
commuter_pass.cpp:126:12: warning: unused variable 'cost' [-Wunused-variable]
  126 |         ll cost=me.first;
      |            ^~~~
commuter_pass.cpp:77:9: warning: variable 'par' set but not used [-Wunused-but-set-variable]
   77 |     int par[n+5];
      |         ^~~

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