Submission #1305196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305196		ngocphu	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	2096 ms	36068 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const long long INF = 2000000000000000000LL;
const int maxN = 2e5 + 4;
const int LOG = 18; // 2^LOG >= numNode
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
const int MOD = 1e9 + 7;
const double PI = 3.14159265;

int n, m, s, t, u, v;
ll ans = INF;
vector<pair<int,int>> E[maxN];
vector<vector<ll>> D(maxN, vector<ll>(3, INF));
vector<vector<ll>> best(maxN, vector<ll>(2, INF));

void dijk(int st, int type)
{
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;

    q.push({0, st});
    D[st][type] = 0;

    while(!q.empty())
    {
        pair<ll,int> h = q.top();q.pop();

        ll w = h.first, u = h.second;

        if (w > D[u][type]) continue;

        for (pair<int,int> x : E[u])
        {
            int v = x.first, weight = x.second;

            if (D[v][type] > D[u][type] + weight)
            {
                D[v][type] = D[u][type] + weight;
                q.push({D[v][type], v});
            }
        }
    }
}

void dfs(int i)
{
    best[i][0] = D[i][1];
    best[i][1] = D[i][2];

    for (pair<int,int> x : E[i])
    {
        int j = x.first, w = x.second;
        if (D[j][0] + w != D[i][0]) continue;

        dfs(j);

        best[i][0] = min(best[i][0], best[j][0]);
        best[i][1] = min(best[i][1], best[j][1]);
    }

    ans = min(ans, D[i][1] + best[i][1]);
    ans = min(ans, D[i][2] + best[i][0]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

//    freopen("BUS.INP","r",stdin);
//    freopen("BUS.OUT","w",stdout);

    cin >> n >> m >> s >> t >> u >> v;

    for (int i = 1; i <= m; ++i)
    {
        int a, b, c; cin >> a >> b >> c;

        E[a].push_back({b, c});
        E[b].push_back({a, c});
    }

    dijk(s, 0);
    dijk(u, 1);
    dijk(v, 2);

    ans = D[v][1];

    dfs(t);

    cout << ans;

    return 0;
}

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