Submission #637062

#	Time	Username	Problem	Language	Result	Execution time	Memory
637062		VasLemmy	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	356 ms	36128 KiB

commuter_pass

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
/*#pragma GCC tarGet ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC tarGet("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const int N = 1e5;
const int maxN = 2e5 + 1;
const int mod = 1e9 + 7;
const int block_size = 700;
const ll infty = 1e18;

struct Tpq
{
    int ver;
    ll val;
};

struct functer
{
    bool operator()(Tpq a,Tpq b)
    {
        return a.val > b.val;
    }
};

int n,m;
int S,T;
int U,V;
vector<pii> adj[maxN];
ll du[maxN];
ll dv[maxN];
ll ds[maxN];
ll dt[maxN];
int x[maxN],y[maxN],w[maxN];

void Read()
{
    cin >> n >> m >> S >> T >> U >> V;
    for(int i = 1;i <= m;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        x[i] = a;
        y[i] = b;
        w[i] = c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
}

void Dijkstra1()
{
    fill(ds + 1,ds + n + 1,infty);
    ds[S] = 0;
    priority_queue<Tpq,vector<Tpq>,functer> q;
    q.push({S,0});
    do
    {
        Tpq pick = q.top();
        q.pop();
        if(ds[pick.ver] != pick.val) continue;
        int u = pick.ver;
        for(pii e : adj[u])
        {
            int v = e.fi;
            ll wt = e.se;
            if(ds[v] > ds[u] + wt)
            {
                ds[v] = ds[u] + wt;
                q.push({v,ds[v]});
            }
        }
    }
    while(!q.empty());
}

void Dijkstra2()
{
    fill(du + 1,du + n + 1,infty);
    du[U] = 0;
    priority_queue<Tpq,vector<Tpq>,functer> q;
    q.push({U,0});
    do
    {
        Tpq pick = q.top();
        q.pop();
        if(du[pick.ver] != pick.val) continue;
        int u = pick.ver;
        for(pii e : adj[u])
        {
            int v = e.fi;
            ll wt = e.se;
            if(du[v] > du[u] + wt)
            {
                du[v] = du[u] + wt;
                q.push({v,du[v]});
            }
        }
    }
    while(!q.empty());
}

void Dijkstra3()
{
    fill(dv + 1,dv + n + 1,infty);
    dv[V] = 0;
    priority_queue<Tpq,vector<Tpq>,functer> q;
    q.push({V,0});
    do
    {
        Tpq pick = q.top();
        q.pop();
        if(dv[pick.ver] != pick.val) continue;
        int u = pick.ver;
        for(pii e : adj[u])
        {
            int v = e.fi;
            ll wt = e.se;
            if(dv[v] > dv[u] + wt)
            {
                dv[v] = dv[u] + wt;
                q.push({v,dv[v]});
            }
        }
    }
    while(!q.empty());
}

void Dijkstra4()
{
    fill(dt + 1,dt + n + 1,infty);
    dt[T] = 0;
    priority_queue<Tpq,vector<Tpq>,functer> q;
    q.push({T,0});
    do
    {
        Tpq pick = q.top();
        q.pop();
        if(dt[pick.ver] != pick.val) continue;
        int u = pick.ver;
        for(pii e : adj[u])
        {
            int v = e.fi;
            ll wt = e.se;
            if(dt[v] > dt[u] + wt)
            {
                dt[v] = dt[u] + wt;
                q.push({v,dt[v]});
            }
        }
    }
    while(!q.empty());
}

vector<int> adj2[maxN];
int deg[maxN];
vector<int> Topo;
int min_u[maxN];
int min_v[maxN];

void Proceed_DAG()
{
    for(int i = 1;i <= m;i++)
    {
        if(ds[x[i]] + w[i] + dt[y[i]] == ds[T])
        {
            adj2[x[i]].push_back(y[i]);
            deg[y[i]]++;
        }
        else if(ds[y[i]] + w[i] + dt[x[i]] == ds[T])
        {
            adj2[y[i]].push_back(x[i]);
            deg[x[i]]++;
        }
    }
    queue<int> q;
    q.push(S);
    do
    {
        int u = q.front();
        q.pop();
        Topo.push_back(u);
        for(int v : adj2[u])
        {
            if(--deg[v] == 0)
            {
                q.push(v);
            }
        }
    }
    while(!q.empty());

    //cout << dt[5];return;

    fill(min_u + 1,min_u + n + 1,infty);
    fill(min_v + 1,min_v + n + 1,infty);
    //min_u[1] = du[1];
    //min_v[1] = dv[1];
    ll res = du[V];
    for(int i : Topo)
    {
        //cout << i <<' ';
        min_u[i] = min(min_u[i],du[i]);
        min_v[i] = min(min_v[i],dv[i]);
        res = min(res,dv[i] + min_u[i]);
        res = min(res,du[i] + min_v[i]);
        for(int j : adj2[i])
        {
            min_u[j] = min(min_u[i],min_u[j]);
            min_v[j] = min(min_v[i],min_v[j]);
        }
    }
    cout << res;
}

void Solve()
{
    Dijkstra1();
    Dijkstra2();
    Dijkstra3();
    Dijkstra4();
    Proceed_DAG();
    //cout << dv[5];
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

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