Submission #555946

#	Time	Username	Problem	Language	Result	Execution time	Memory
555946		fadi57	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	399 ms	25020 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[2][mx];ll l;

 void dikjstra(int node,int cnt)
      {
   priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater < pair<ll,int> >>q;
   for(int i=0; i<=n; i++)
    {
        dist[cnt][i]=inf;
    }
    q.push({0,node});
    dist[cnt][node]=0;
    while(!q.empty())
    {
        pair<ll,int>me=q.top();
        q.pop();
        int x=me.second;

        ll cost=me.first;
       for(auto it:adj[x])
        {
            int node2=it.first;
           if(cost+it.second<dist[cnt][it.first])
            {   ll cost2=cost+it.second;
                dist[cnt][it.first]=cost2;
                q.push({(cost2),node2});

            }

        }

    }
 }
 void dikjstra2(int node,int cnt)
      {

     priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater < pair<ll,int> >>q;
       bool vis[n+9];
    for(int i=0; i<=n; i++)
    {
       // dist[cnt][i]=inf;
       vis[i]=0;
    }
    q.push({0,node});
   
     while(!q.empty())
     {
        pair<ll,int>me=q.top();
        q.pop();
        int x=me.second;
        if(vis[x]){
            continue;
        }
        vis[x]=1;
        ll cost=me.first;

       dp[cnt][x]=min(dist[3][x],dp[cnt][x]);

        for(auto it:adj[x])
        {
            int node2=it.first;

            if(cost+it.second<=dist[cnt][it.first])
            {
               dp[cnt][node2]=min( dp[cnt][node2],dp[cnt][x]);

                ll cost2=cost+it.second;
            

                q.push({(cost2),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(v,3);
    dikjstra(u,2);


    dikjstra(s,0);
    dikjstra(t,1);


    l=dist[0][t];


    for(int i=1; i<=n; i++)
    {
        dp[0][i]=dp[1][i]=inf;
    }
    dikjstra2(t,1);
    dikjstra2(s,0);

    ll ans=inf;


    for(int i=1; i<=n; i++)
    {
        if(dist[0][i]+dist[1][i]==l)
        {

           ans=min(dist[2][i]+dp[0][i],ans);
           ans=min(dist[2][i]+dp[1][i],ans);

    }
    }

    ans=min(ans,dist[2][v]);
    cout<<ans;

}

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