Submission #1278024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278024		hoangtien69	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	214 ms	20148 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5 + 5;
#define pii pair<int, int>
const int INF = 1e18;

int n, m;
int U, V, S, T;
vector<pii> adj[MAXN];
int du[MAXN];
int dv[MAXN];
int ds[MAXN];
int dp[2][MAXN];

void dijskstra1(int st, int d[])
{
    for (int i = 1; i <= n; i++)
    {
        d[i] = INF;
    }
    d[st] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({d[st], st});
    while(!pq.empty())
    {
        auto[dist, u] = pq.top();
        pq.pop();
        if (dist > d[u]) continue;

        for (auto[v, w] : adj[u])
        {
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
}
int dijskstra2(int s, int t)
{
    for (int i = 1; i <= n; i++)
    {
        dp[0][i] = INF;
        dp[1][i] = INF;
        ds[i] = INF;
    }
    ds[s] = 0;
    dp[0][s] = du[s];
    dp[1][s] = dv[s];

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({ds[s], s});

    while(!pq.empty())
    {
        auto[dist, u] = pq.top();
        pq.pop();
        if (dist > ds[u]) continue;

        for (auto[v, w] : adj[u])
        {
            if (ds[v] > ds[u] + w)
            {
                ds[v] = ds[u] + w;
                dp[0][v] = min(dp[0][u], du[v]);
                dp[1][v] = min(dp[1][u], dv[v]);
                pq.push({ds[v], v});
            }
            else if (ds[v] == ds[u] + w)
            {
                int old_sum = dp[0][v] + dp[1][v];
                int new_sum = min(dp[0][u], du[v]) + min(dp[1][u], dv[v]);

                if (new_sum < old_sum)
                {
                    dp[0][v] = min(dp[0][u], du[v]);
                    dp[1][v] = min(dp[1][u], dv[v]);
                }
            }
        }
    }
    return dp[0][t] + dp[1][t];
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    cin >> S >> T;
    cin >> U >> V;
    for (int i = 1; i <= m; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
    dijskstra1(U, du);
    dijskstra1(V, dv);
    int res = du[V];
    cout << min({res, dijskstra2(S, T), dijskstra2(T, S)});
}

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