Submission #696737

#	Time	Username	Problem	Language	Result	Execution time	Memory
696737		ToroTN	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	428 ms	25164 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define X first 
#define Y second
ll n,m,S,T,U,V,u_i,v_i,w_i,fromu[100005],fromv[100005],u,y,cost,froms[100005],fromt[100005];
ll ans,us[100005],vs[100005],ut[100005],vt[100005];
vector<pair<ll,ll> > v[100005];
priority_queue<pair<ll,ll> > pq;
void debug_arr(ll arr[])
{
    for(int i=1;i<=n;i++)
    {
        printf("%lld ",arr[i]);
    }
    printf("\n");
}
void dij(ll st,ll d[])
{
    for(int i=1;i<=n;i++)d[i]=1e18;
    d[st]=0;
    pq.push({0,st});
    while(!pq.empty())
    {
        u=pq.top().Y;
        pq.pop();
        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;
                pq.push({-d[y],y});
            }
        }        
    }
}
void dij2(ll st,ll d[],ll du[],ll dv[])
{
    for(int i=1;i<=n;i++)d[i]=1e18,du[i]=1e18,dv[i]=1e18;
    d[st]=0,du[st]=fromu[st],dv[st]=fromv[st];
    pq.push({0,st});
    while(!pq.empty())
    {
        u=pq.top().Y;
        pq.pop();
        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;
                du[y]=min(du[u],fromu[y]);
                dv[y]=min(dv[u],fromv[y]);
                pq.push({-d[y],y});
            }else if(d[u]+cost==d[y])
            {
                du[y]=min(du[y],min(du[u],fromu[y]));
                dv[y]=min(dv[y],min(dv[u],fromv[y]));
            }
        }        
    }
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n >> m >> S >> T >> U >> V;
    for(int i=1;i<=m;i++)
    {
        cin >> u_i >> v_i >> w_i;
        v[u_i].pb({v_i,w_i});
        v[v_i].pb({u_i,w_i});
    }
    dij(U,fromu);
    dij(V,fromv);
    ans=fromu[V];
    /*printf("basic\n");
    debug_arr(fromu),debug_arr(fromv);*/
    dij2(S,froms,us,vs);
    dij2(T,fromt,ut,vt);
    /*printf("s\n");
    debug_arr(froms),debug_arr(us),debug_arr(vs);
    printf("t\n");
    debug_arr(fromt),debug_arr(ut),debug_arr(vt);*/
    for(int i=1;i<=n;i++)
    {
        if(froms[i]+fromt[i]==froms[T])
        {
            ans=min(ans,us[i]+vt[i]);
            ans=min(ans,ut[i]+vs[i]);
        }
    }
    printf("%lld\n",ans);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dij(long long int, long long int*)':
commuter_pass.cpp:28: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]
   28 |         for(int i=0;i<v[u].size();i++)
      |                     ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void dij2(long long int, long long int*, long long int*, long long int*)':
commuter_pass.cpp:48: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]
   48 |         for(int i=0;i<v[u].size();i++)
      |                     ~^~~~~~~~~~~~

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