제출 #1090738

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1090738		_callmelucian	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	255 ms	29272 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
vector<pl> adj[mn];
bool vis[mn];

void dijkstra (int source, vector<ll> &dist, int n) {
    for (int i = 1; i <= n; i++)
        vis[i] = 0, dist[i] = LLONG_MAX;
    dist[source] = 0;

    priority_queue<pl> pq; pq.emplace(0, source);
    while (pq.size()) {
        int a = pq.top().second; pq.pop();
        if (vis[a]) continue;
        vis[a] = 1;
        for (pl it : adj[a]) {
            int b; ll w; tie(b, w) = it;
            if (dist[a] + w < dist[b]) {
                dist[b] = dist[a] + w;
                pq.emplace(-dist[b], b);
            }
        }
    }
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    vector<tt> edge(m);
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        edge[i] = {a, b, c};
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }

    vector<ll> distS(n + 1), distT(n + 1), distU(n + 1), distV(n + 1), dist(n + 1);
    dijkstra(S, distS, n);
    dijkstra(T, distT, n);
    dijkstra(U, distU, n);
    dijkstra(V, distV, n);

    ll ans = LLONG_MAX;

    // S -> T direction
    for (int i = 1; i <= n; i++) adj[i].clear();
    for (int i = 1; i <= n; i++) {
        if (distU[i] != LLONG_MAX)
            adj[U].emplace_back(i, distU[i]);
        if (distV[i] != LLONG_MAX)
            adj[i].emplace_back(V, distV[i]);
    }
    for (int i = 0; i < m; i++) {
        int a, b, c; tie(a, b, c) = edge[i];
        if (max(distS[a], distT[b]) != LLONG_MAX)
            if (distS[a] + c + distT[b] == distS[T]) adj[a].emplace_back(b, 0);
        if (max(distS[b], distT[a]) != LLONG_MAX)
            if (distS[b] + c + distT[a] == distS[T]) adj[b].emplace_back(a, 0);
    }
    dijkstra(U, dist, n);
    ans = min(ans, dist[V]);

    // T -> S direction
    for (int i = 1; i <= n; i++) adj[i].clear();
    for (int i = 1; i <= n; i++) {
        if (distU[i] != LLONG_MAX)
            adj[U].emplace_back(i, distU[i]);
        if (distV[i] != LLONG_MAX)
            adj[i].emplace_back(V, distV[i]);
    }
    for (int i = 0; i < m; i++) {
        int a, b, c; tie(a, b, c) = edge[i];
        if (max(distT[a], distS[b]) != LLONG_MAX)
            if (distT[a] + c + distS[b] == distT[S]) adj[a].emplace_back(b, 0);
        if (max(distT[b], distS[a]) != LLONG_MAX)
            if (distT[b] + c + distS[a] == distT[S]) adj[b].emplace_back(a, 0);
    }
    dijkstra(U, dist, n);
    ans = min(ans, dist[V]);

    cout << ans;

    return 0;
}

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