제출 #1305663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305663		ngocphu	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	415 ms	48288 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const long long INF = 2000000000000000000LL;
const int maxN = 1e5 + 4;
const int LOG = 18;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
const int MOD = 1e9 + 7;
const int base = 311;

int n, m, s, t, x, y;
vector<pair<int,int>> E[maxN], G[4 * maxN];
ll D[2][maxN], P[4 * maxN];

void dijk(int st, int k)
{
    for (int i = 1; i <= n; ++i) D[k][i] = 1e18;

    D[k][st] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
    q.push({0, st});

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

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

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

        for (pair<int,int> x : E[u])
        {
            int v = x.first, weight = x.second;
            if (D[k][v] > D[k][u] + weight)
            {
                D[k][v] = D[k][u] + weight;
                q.push({D[k][v], v});
            }
        }
    }
}

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

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

    cin >> n >> m >> s >> t >> x >> y;

    for (int i = 1; i <= m; ++i)
    {
        int u, v, w; cin >> u >> v >> w;

        E[u].push_back({v, w});
        E[v].push_back({u, w});
    }

    dijk(s, 0);
    dijk(t, 1);

    for (int u = 1; u <= n; ++u)
    {
        G[u].push_back({n + u, 0});
        G[u].push_back({2 * n + u, 0});
        G[n + u].push_back({3 * n + u, 0});
        G[2 * n + u].push_back({3 * n + u, 0});

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

            if (D[0][u] + w + D[1][v] == D[0][t])
            {
                G[n + u].push_back({n + v, 0});
                G[2 * n + v].push_back({2 * n + u, 0});
            }

            G[u].push_back({v, w});
            G[3 * n + u].push_back({3 * n + v, w});
        }
    }

    for (int i = 1; i <= 4 * n; ++i) P[i] = 1e18;
    P[x] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;

    q.push({0, x});

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

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

        if (w > P[u]) continue;

        for (pair<int,int> x : G[u])
        {
            int v = x.first, weight = x.second;
            if (P[v] > P[u] + weight)
            {
                P[v] = P[u] + weight;
                q.push({P[v], v});
            }
        }
    }

    cout << P[3 * n + y];

    return 0;
}

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