Submission #684080

#	Time	Username	Problem	Language	Result	Execution time	Memory
684080		overwatch9	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	420 ms	21728 KiB

commuter_pass

#include <bits/stdc++.h>
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[MAX_N];
bool processed[MAX_N];
void bfs(int s) {
    fill(dis, dis + MAX_N, INT_MAX);
    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;
            int w = i.second;
            int new_dis = dis[a];
            if (!on_commuter[a] || !on_commuter[b])
                new_dis += w;
            if (new_dis <= dis[b]) {
                parent[b].push_back(a);
                if (dis[b] > new_dis)
                    pq.push({-new_dis, b});
                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});
    }
    bfs(S);
    get_commuter_stations(T);
    bfs(U);
    cout << dis[V] << '\n';
}

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