Submission #517141

#	Time	Username	Problem	Language	Result	Execution time	Memory
517141		status_coding	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	667 ms	28112 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

long long n,m,s,t,a,b,ans;
vector<pair<long long, long long>> v[100005];

long long len[100005][4];
long long dp[100005][2];

void djikstra(int s, int nr)
{
    for(int i=1;i<=n;i++)
        len[i][nr] = 1e18;

    multiset<pair<long long, long long>> mul;
    mul.insert({0, s});

    while(!mul.empty())
    {
        long long p = mul.begin()->second;
        long long val = mul.begin()->first;
        mul.erase(mul.begin());

        if(len[p][nr] != 1e18)
            continue;

        len[p][nr] = val;

        for(auto it : v[p])
        {
            if(len[it.first][nr] != 1e18)
                continue;

            mul.insert({val + it.second, it.first});
        }
    }
}

void calcDp0(int p)
{
    if(dp[p][0] != 1e18)
        return;

    dp[p][0] = len[p][1];

    for(auto it : v[p])
        if(len[p][0] - it.second == len[it.first][0])
        {
            calcDp0(it.first);
            dp[p][0] = min(dp[p][0], dp[it.first][0]);
        }
}

void calcDp1(int p)
{
    if(dp[p][1] != 1e18)
        return;

    dp[p][1] = len[p][1];

    for(auto it : v[p])
        if(len[p][0] + it.second == len[it.first][0] && dp[it.first][0] != 1e18)
        {
            calcDp1(it.first);
            dp[p][1] = min(dp[p][1], dp[it.first][1]);
        }
}

int main()
{
    cin>>n>>m>>s>>t>>a>>b;

    for(int i=1;i<=m;i++)
    {
        int x, y, c;
        cin>>x>>y>>c;

        v[x].push_back({y, c});
        v[y].push_back({x, c});
    }

    djikstra(t, 0);
    djikstra(b, 1);
    djikstra(a, 2);

    ans = len[a][1];

    for(int i=1;i<=n;i++)
        dp[i][0] = dp[i][1] = 1e18;

    calcDp0(s);
    calcDp1(t);

    for(int i=1;i<=n;i++)
        ans = min(ans, min(dp[i][0], dp[i][1]) + len[i][2]);

    cout<<ans;
    return 0;
}

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