Submission #1189744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189744		DangKhoizzzz	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	250 ms	26568 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>
#define arr4 array <int , 4>

/*
+ array limit ???
+ special case ??? n = 1?
+ time limit ???
*/

using namespace std;

const int INF = 1e18 + 7;
const int maxn = 2e5 + 7;

int n , m;
int S , T;
int U , V;

int ans = INF;

vector <pii> g[maxn];
vector <int> du , dv;

vector <int> dijkstra(int start)
{
    vector <int> d(maxn , INF);
    vector <bool> vis(maxn , false);

    priority_queue <pii , vector <pii> , greater <pii>> PQ;
    d[start] = 0;
    PQ.push({0 , start});

    while(!PQ.empty())
    {
        int u = PQ.top().se;
        PQ.pop();
        if(vis[u]) continue;
        vis[u] = 1;

        for(pii edge: g[u])
        {
            int v = edge.fi;
            int w = edge.se;
            if(d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                PQ.push({d[v] , v});
            }
        }
    }
    return d;
}

vector <pii> dijkstra2(int start)
{
    vector <pii> d(n+1 , {INF , INF});
    vector <bool> vis(n+1 , false);
    priority_queue <pii , vector <pii> , greater <pii>> PQ;
    PQ.push({0 , start});
    d[start] = (pii){0 , du[start]};

    while(!PQ.empty())
    {
        int u = PQ.top().se;
        PQ.pop();

        if(vis[u]) continue;
        vis[u] = 1;

        for(pii tmp: g[u])
        {
            int v = tmp.fi , w = tmp.se;

            if(d[v].fi > d[u].fi + w)
            {
                d[v].fi = d[u].fi + w;
                d[v].se = min(d[u].se , du[v]);
                PQ.push({d[v].fi , v});
            }
            else if(d[v].fi == d[u].fi + w)
            {
                d[v].se = min({d[v].se , d[u].se , du[v]});
            }
        }
    }
    return d;
}

void solve()
{
    cin >> n >> m;
    cin >> S >> T;
    cin >> U >> V;
    for(int i = 1; i <= m; i++)
    {
        int u , v , w;
        cin >> u >> v >> w;
        g[u].push_back({v , w});
        g[v].push_back({u , w});
    }
    du = dijkstra(U);
    dv = dijkstra(V);

    int ans = INF;
    
    vector <pii> ds = dijkstra2(S);
    swap(du , dv);
    vector <pii> dt = dijkstra2(T);

    for(int i = 1; i <= n; i++)
    {
        if(ds[i].fi + dt[i].fi == ds[T].fi)
        {
            ans = min(ans , ds[i].se + dt[i].se);
        }
    }

    ds = dijkstra2(S);
    swap(du , dv);
    dt = dijkstra2(T);

    for(int i = 1; i <= n; i++)
    {
        if(ds[i].fi + dt[i].fi == ds[T].fi)
        {
            ans = min(ans , ds[i].se + dt[i].se);
        }
    }

    cout << min(du[V] , ans) << '\n';

}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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