Submission #684431

#	Time	Username	Problem	Language	Result	Execution time	Memory
684431		overwatch9	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	411 ms	21784 KiB

commuter_pass

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using ll = long long;
const int MAX_N = 1e5 + 1;
vector <pair <int, int>> adj[MAX_N];
int N, M, S, T, U, V;
bool on_commuter[MAX_N];
vector <int> parent[MAX_N];
ll dis_from_U[MAX_N], dis_from_V[MAX_N], dis_from_T[MAX_N];
bool processed[MAX_N];
void dijkstra(int s, ll dis[]) {
    fill(dis, dis + MAX_N, 1e17);
    fill(processed, processed + MAX_N, false);
    dis[s] = 0;
    priority_queue <pair <ll, int>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        int a = pq.top().second;
        pq.pop();
        if (processed[a])
            continue;
        processed[a] = true;
        for (auto i : adj[a]) {
            int b = i.first;
            ll w = i.second;
            ll new_dis = dis[a];
            if (!on_commuter[a] || !on_commuter[b])
                new_dis += w;
            if (new_dis <= dis[b]) {
                if (new_dis < dis[b]) {
                    pq.push({-new_dis, b});
                    parent[b].clear();
                }
                parent[b].push_back(a);
                dis[b] = new_dis;
            }
        }
    }
}
void get_commuter_stations(int s) {
    if (on_commuter[s])
        return;
    on_commuter[s] = true;
    for (auto i : parent[s]) {
        get_commuter_stations(i);
    }
}
int main() {
    cin >> N >> M >> S >> T >> U >> V;
    for (int i = 0; i < M; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    dijkstra(T, dis_from_T);
    get_commuter_stations(S);
    dijkstra(V, dis_from_V);
    dijkstra(U, dis_from_U);
    ll ans = dis_from_V[U];
    for (int i = 1; i <= N; i++) {
        ans = min(ans, dis_from_U[i] + dis_from_V[i]);
    }
    cout << ans << '\n';
}

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