Submission #673455

#	Time	Username	Problem	Language	Result	Execution time	Memory
673455		ToroTN	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2085 ms	13804 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
#define ll long long
ll n,m,S,T,U,V,a,b,c,disu[100005],disv[100005],dp[100005],ans=1e18,d[100005],u,node,cost,y;
ll dp2[100005],d2[100005],w;
vector<pair<ll,ll> > v[100005];
priority_queue<pair<ll,ll> > pq;
void dij(ll st,ll dis[])
{
    for(int i=1;i<=n;i++)dis[i]=1e18;
    dis[st]=0;
    pq.push({0,st});
    while(!pq.empty())
    {
        u=pq.top().Y;
        w=-pq.top().X;
        if(w>dis[u])continue;
        pq.pop();
        for(int i=0;i<v[u].size();i++)
        {
            node=v[u][i].X,cost=v[u][i].Y;
            if(dis[u]+cost<dis[node])
            {
                dis[node]=dis[u]+cost;
                pq.push({-dis[node],node});
            }
        }
    }
}
int main()
{
    scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&S,&T,&U,&V);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&a,&b,&c);
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    dij(U,disu),dij(V,disv);
    for(int i=1;i<=n;i++)dp[i]=1e18,d[i]=1e18,d2[i]=1e18,dp2[i]=1e18;
    dp[S]=disu[S],d[S]=0;
    ans=min(ans,disu[S]+disv[S]);
    pq.push({-d[S],S});
    while(!pq.empty())
    {
        u=pq.top().Y;
        pq.pop();
        w=-pq.top().X;
        //printf("%lld %lld\n",u,w);
        //if(w>d[u])continue;
        for(int i=0;i<v[u].size();i++)
        {
            y=v[u][i].X,cost=v[u][i].Y;
            if(d[u]+cost<d[y])
            {
                d[y]=d[u]+cost;
                dp[y]=min(dp[y],min(dp[u],disu[y]));
                pq.push({-d[y],y});
            }
            if(d[u]+cost==d[y])dp[y]=min(dp[y],min(dp[u],disu[y]));
        }
    }
    dp2[T]=disu[T],d2[T]=0;
    ans=min(ans,disu[T]+disv[T]);
    pq.push({-d2[T],T});
    while(!pq.empty())
    {
        u=pq.top().Y;
        pq.pop();
        w=-pq.top().X;
        //printf("%lld %lld\n",u,w);
        //if(w>d2[u])continue;
        for(int i=0;i<v[u].size();i++)
        {
            y=v[u][i].X,cost=v[u][i].Y;
            if(d2[u]+cost<d2[y])
            {
                d2[y]=d2[u]+cost;
                dp2[y]=min(dp2[y],min(dp2[u],disu[y]));
                pq.push({-d2[y],y});
            }
            if(d2[u]+cost==d2[y])dp2[y]=min(dp2[y],min(dp2[u],disu[y]));
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(d[i]+d2[i]==d[T])
        {
            ans=min(ans,min(dp[i],dp2[i])+disv[i]);
        }
    }
    ans=min(ans,disv[U]);
    printf("%lld\n",ans);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dij(long long int, long long int*)':
commuter_pass.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int i=0;i<v[u].size();i++)
      |                     ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int i=0;i<v[u].size();i++)
      |                     ~^~~~~~~~~~~~
commuter_pass.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int i=0;i<v[u].size();i++)
      |                     ~^~~~~~~~~~~~
commuter_pass.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&S,&T,&U,&V);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%lld%lld%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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