Submission #854415

#	Time	Username	Problem	Language	Result	Execution time	Memory
854415		how2read	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	340 ms	31340 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
int n,m,S,T,U,V;
vector<pair<int,long long>> edge[100005];
long long ds[100005], dt[100005], du[100005][2][2], dv[100005][2][2];

struct hi {
    int x;
    long long v;
    int free;
    int check;
};

bool operator > (const hi& x1, const hi& x2)
{
    return x1.v > x2.v;
}
bool operator < (const hi& x1, const hi& x2)
{
    return x1.v < x2.v;
}

void dij(int s, long long d[100005])
{
    priority_queue<pair<long long,int>, vector<pair<long long, int>>, greater<pair<long long, int>> > q;
    q.push({0,s});
    for(int i=1;i<=n;i++)
        d[i] = LLONG_MAX;
    d[s] = 0;

    while(q.size() > 0)
    {
        int x = q.top().second;
        long long vx = q.top().first;
        q.pop();

        if(d[x] < vx)
            continue;

        for(auto i : edge[x])
        {
            int v = i.first;
            int vv = i.second;

            if(d[v] > d[x] + vv)
            {
                d[v] = d[x] + vv;
                q.push({d[v], v});
            }
        }
    }
}

void doo(int s, int t, long long d[100005][2][2])
{
    priority_queue<hi, vector<hi>, greater<hi>> q;
    q.push({s,0,0,0});
    for(int i=1;i<=n;i++)
    {
        d[i][0][0] = LLONG_MAX;
        d[i][1][0] = LLONG_MAX;
        d[i][0][1] = LLONG_MAX;
    }
    d[s][0][0] = 0;
    d[s][1][0] = 0;
    d[s][0][1] = 0;

    while(q.size() > 0)
    {
        int x = q.top().x;
        long long vx = q.top().v;
        int free = q.top().free;
        int check = q.top().check;
        q.pop();

        if(vx > d[x][free][check])
            continue;

        //if(x == t)
            //return;

        for(auto i : edge[x])
        {
            int v = i.first;
            int vv = i.second;

            if(d[v][0][check] > d[x][free][check] + vv)
            {
                d[v][0][check] = d[x][free][check] + vv;
                q.push({v, d[v][0][check], 0, check});
            }

            if(check == 1)
                continue;

            if(ds[x] + vv + dt[v] == ds[T])
            {
                if(d[v][1][0] > d[x][free][check])
                {
                    d[v][1][0] = d[x][free][check];
                    q.push({v, d[v][1][0], 1, 0});
                }
                else if(free == 1)
                {
                    if(d[v][0][1] > d[x][free][check] + vv)
                    {
                        d[v][0][1] = d[x][free][check] + vv;
                        q.push({v, d[v][0][1], 0, 1});
                    }
                }
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    cin>>S>>T>>U>>V;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        edge[x].push_back({y,z});
        edge[y].push_back({x,z});
    }

    dij(S,ds);
    dij(T,dt);
    doo(U,V,du);
    doo(V,U,dv);

    long long res = min(du[V][0][0], dv[U][0][0]);
    res = min(res,min(du[V][1][0], dv[U][1][0]));
    res = min(res, min(du[V][0][1], dv[U][0][1]));
    cout<<res;

    return 0;
}

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