Submission #556541

#	Time	Username	Problem	Language	Result	Execution time	Memory
556541		hibiki	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	426 ms	29548 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;

#define PB push_back
#define F first
#define S second

const int N=100010;
int n,m,s,t,u,v,in_d[N];
long long best[2][N];
vector<long long> cost[4];
vector<int> eg_topo[N];
vector<pair<pair<int,int>,long long> > eg_l;
vector<pair<int,long long> > vec[N];


void ssp(int st,vector<long long> &node)
{
    node.resize(n+5,1e18);

    priority_queue<pair<long long,int> > pq;
    pq.push({-0,st});
    node[st]=0;

    while(!pq.empty())
    {
        long long val=-pq.top().F;
        int nw=pq.top().S;
        pq.pop();

        for(auto go:vec[nw])
        {
            int go_p=go.F;
            long long go_cost=val+go.S;

            if(node[go_p]>go_cost)
            {
                node[go_p]=go_cost;
                pq.push({-go_cost,go_p});
            }
        }
    }

    return ;
}

int main()
{
    scanf("%d %d",&n,&m);
    scanf("%d %d",&s,&t);
    scanf("%d %d",&u,&v);
    for(int i=0;i<m;i++)
    {
        int a,b;
        long long c;
        scanf("%d %d %lld",&a,&b,&c);
        vec[a].PB({b,c});
        vec[b].PB({a,c});
        eg_l.PB({{a,b},c});
    }

    ssp(s,cost[0]);
    ssp(t,cost[1]);
    ssp(u,cost[2]);
    ssp(v,cost[3]);

    for(int i=0;i<m;i++)
    {
        int a=eg_l[i].F.F,b=eg_l[i].F.S;
        long long val=eg_l[i].S;
        if(cost[0][a]>cost[0][b])swap(a,b);
        if(cost[0][a]+cost[1][b]+val==cost[0][t])
        {
            in_d[b]++;
            eg_topo[a].PB(b);
        }
    }

    long long ans=cost[2][v];
    for(int i=1;i<=n;i++)
    {
        best[0][i]=cost[2][i];
        best[1][i]=cost[3][i];
        ans=min(ans,best[0][i]+best[1][i]);
    }
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int nw=q.front();
        q.pop();

        for(auto go:eg_topo[nw])
        {
            // printf("nw:%d go:%d\n",nw,go);
            // printf("%lld %lld\n",cost[2][go],best[1][nw]);
            // printf("%lld %lld\n",cost[3][go],best[0][nw]);
            ans=min(ans,cost[2][go]+best[1][nw]);
            ans=min(ans,cost[3][go]+best[0][nw]);
            best[0][go]=min(best[0][go],best[0][nw]);
            best[1][go]=min(best[1][go],best[1][nw]);
            in_d[go]--;
            if(!in_d[go])
                q.push(go);
        }
    }
    printf("%lld\n",ans);

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d %d",&s,&t);
      |     ~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d %d",&u,&v);
      |     ~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d %d %lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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