제출 #510069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
510069		blue	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	794 ms	28740 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pl = pair<ll, ll>;

const int maxN = 100'000;
const ll INF = 1'000'000'000'000'000'000LL;

int N, M;
int S, T, U, V;

vector<pl> edge[1+maxN];

vll dijkstra(int src)
{
    vll dist(1+N, INF);
    dist[src] = 0;

    set<pl> tbv;
    for(int i = 1; i <= N; i++) tbv.insert({dist[i], i});

    while(!tbv.empty())
    {
        int u = tbv.begin()->second;
        tbv.erase(tbv.begin());

        for(pl e: edge[u])
        {
            int v = e.first;
            ll w = e.second;

            if(dist[v] <= dist[u] + w) continue;

            tbv.erase({dist[v], v});
            dist[v] = dist[u] + w;
            tbv.insert({dist[v], v});
        }
    }

    return dist;
}

vll dist[1+maxN];

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

    cin >> N >> M;
    cin >> S >> T;
    cin >> U >> V;

    for(int j = 1; j <= M; j++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edge[a].push_back({b, c});
        edge[b].push_back({a, c});
    }

    // vll dist
    for(int src: {U, V, S, T}) dist[src] = dijkstra(src);

    vi spv;
    for(int i = 1; i <= N; i++)
        if(dist[S][i] + dist[T][i] == dist[S][T])
            spv.push_back(i);

    sort(spv.begin(), spv.end(), [] (int u, int v)
    {
        return dist[S][u] < dist[S][v];
    });

    ll ans = dist[U][V];

    vll dpU(1+N, INF), dpV(1+N, INF);

    for(int u: spv)
    {
        dpU[u] = dist[U][u];
        dpV[u] = dist[V][u];

        for(pl e: edge[u])
        {
            int v = e.first;
            ll w = e.second;
            if(dist[S][v] + w + dist[T][u] != dist[S][T]) continue;
            dpU[u] = min(dpU[u], dpU[v]);
            dpV[u] = min(dpV[u], dpV[v]);
        }

        ans = min(ans, dpU[u] + dist[V][u]);
        ans = min(ans, dpV[u] + dist[U][u]);
    }

    cout << ans << '\n';
}

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