Submission #718269

#	Time	Username	Problem	Language	Result	Execution time	Memory
718269		ovidiush11	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2061 ms	262144 KiB

commuter_pass

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

#define ll long long
#define ff first
#define ss second

const ll N = 1e5+7;

ll pos[4],dis[4][N],n,m;
vector<vector<pair<ll,ll>>> a;

void dijkstra(ll p)
{
    priority_queue<pair<ll,ll>> pq;
    pq.push({0,pos[p]});
    for(ll i = 0;i < n;i++)dis[p][i] = 1e18;
    while(!pq.empty())
    {
        pair<ll,ll> v = pq.top();
        pq.pop();
        v.ff *= -1;
        if(v.ff >= dis[p][v.ss])continue;
        dis[p][v.ss] = v.ff;
        for(auto x : a[v.ss])pq.push(make_pair(-(v.ff + x.ff),x.ss));
    }
    return ;
}

ll in[N];

void check(ll p)
{
    for(ll i = 0;i < n;i++)in[i] = 0;
    queue<ll> q;
    q.push(p);
    in[p] = 1;
    while(!q.empty())
    {
        ll v = q.front();
        q.pop();
        for(auto x : a[v])
        {
            if(dis[1][v] < dis[1][x.ss] && dis[0][x.ss] + dis[1][x.ss] == dis[1][pos[0]] && !in[x.ss])
            {
                in[x.ss] = 1;
                q.push(x.ss);
            }
        }
    }
}

ll dismin[N];

void getmin(ll s)
{
    queue<pair<ll,ll>> q;
    q.push(make_pair(dis[2][pos[s]],pos[s]));
    while(!q.empty())
    {
        pair<ll,ll> v = q.front();
        q.pop();
        v.ff = min(v.ff,dis[2][v.ss]);
        dismin[v.ss] = min(dismin[v.ss],v.ff);
        for(auto x : a[v.ss])if(in[x.ss] && dis[s][x.ss] > dis[s][v.ss])q.push(make_pair(v.ff,x.ss));
    }
    return ;
}

int main()
{
    cin>>n>>m;
    cin>>pos[0]>>pos[1]>>pos[2]>>pos[3];
    pos[0]--;pos[1]--;pos[2]--;pos[3]--;
    a.resize(n);
    for(ll i = 0;i < m;i++)
    {
        ll x,y,z;
        cin>>x>>y>>z;x--;y--;
        a[x].push_back(make_pair(z,y));
        a[y].push_back(make_pair(z,x));
    }
    for(ll i = 0;i < n;i++)dismin[i] = 1e18;
    dijkstra(0);dijkstra(1);dijkstra(2);dijkstra(3);
    check(pos[1]);
    getmin(0);
    getmin(1);
    ll ans = dis[2][pos[3]];
    for(ll i = 0;i < n;i++)if(in[i])ans = min(dismin[i] + dis[3][i],ans);
    cout<<ans;
    return 0;
}

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