Submission #1286745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286745		harryleee	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	2097 ms	327680 KiB

commuter_pass

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5;
int n, m, st, en, shop1, shop2;
struct line{
    int u, v, w, id;
};
line l[2 * maxn + 1];
vector<line> adj[maxn + 1];
bool on_road[2 * maxn + 1];
vector<long long> dis_st, dis_en, dis_shop1, dis_shop2;

struct str{
    bool operator ()(const pair<int, long long>& x, const pair<int, long long>& y) const {
        return x.second > y.second;
    }
};

inline vector<long long> dijkstra(int st){
    vector<long long> ans(n + 1 , 1e18);
    ans[st] = 0;
    priority_queue<pair<int, long long>, vector<pair<int, long long>>, str> pq;
    pq.push({st, 0});
    while(!pq.empty()){
        int u = pq.top().first, dis = pq.top().second;
        pq.pop();
        if (dis > ans[u]) continue;
        for (line l : adj[u]){
            int nxt = (u == l.u) ? l.v : l.u;
            int w = l.w;
            if (dis + w < ans[nxt]){
                ans[nxt] = dis + w;
                pq.push({nxt, ans[nxt]});
            } 
        }
    }
    return ans;
}

inline long long solve(long long res){
    vector<bool> vis(n + 1, false);
    queue<pair<int, long long>> pq;
    pq.push({st, dis_shop1[st]});
    while(!pq.empty()){
        int u = pq.front().first;
        long long dis = pq.front().second;
        pq.pop();
        dis = min(dis, dis_shop1[u]);
        res = min(res, dis + dis_shop2[u]);
        for (line ln : adj[u]) if (on_road[ln.id]){
            int nxt = (u == ln.u) ? ln.v : ln.u;
            if (dis_st[u] + ln.w != dis_st[nxt]) continue;
            pq.push({nxt, dis});
        }
    }
    return res;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> st >> en >> shop1 >> shop2;
    for (int i = 1; i <= m; ++i){
        cin >> l[i].u >> l[i].v >> l[i].w;
        l[i].id = i;
        adj[l[i].u].push_back(l[i]);
        adj[l[i].v].push_back(l[i]);
    }

    dis_st = dijkstra(st);
    dis_en = dijkstra(en);
    dis_shop1 = dijkstra(shop1);
    dis_shop2 = dijkstra(shop2);

    for (int i = 1; i <= m; ++i){
        int u = l[i].u, v = l[i].v, w = l[i].w;
        if (dis_st[u] + dis_en[v] + w == dis_st[en] || dis_st[v] + dis_en[u] + w == dis_st[en])
            on_road[l[i].id] = true;
    }

    long long res = solve(dis_shop1[shop2]);
    swap(dis_shop1, dis_shop2);
    res = min(res, solve(dis_shop1[shop1]));
    cout << res;
}

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