Submission #1176572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176572		Hamed_Ghaffari	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	231 ms	21908 KiB

commuter_pass

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int MXN = 1e5+5;
const ll inf = 1e18;

int n, m, S, T, U, V;
vector<pii> g[MXN];
ll dis[6][MXN];

inline void dijkstra(int v, int id) {
    fill(dis[id]+1, dis[id]+n+1, inf);
    dis[id][v] = 0;
    priority_queue<pll> pq;
    pq.push({0, v});
    while(!pq.empty()) {
        ll d = -pq.top().first;
        int v = pq.top().second;
        pq.pop();
        if(d!=dis[id][v]) continue;
        for(auto [u, w] : g[v])
            if(dis[id][u]>d+w)
                pq.push({-(dis[id][u]=d+w), u});
    }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m >> S >> T >> U >> V;
    for(int i=0,u,v,w; i<m; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dijkstra(S, 0);
    dijkstra(T, 1);
    fill(dis[2]+1, dis[2]+n+1, inf);
    fill(dis[3]+1, dis[3]+n+1, inf);
    fill(dis[4]+1, dis[4]+n+1, inf);
    fill(dis[5]+1, dis[5]+n+1, inf);
    priority_queue<pair<ll, pii>> pq;
    dis[2][U] = 0; pq.push({0, {2, U}});
    if(dis[0][U]+dis[1][U]==dis[0][T]) 
        dis[3][U] = 0, pq.push({0, {3, U}});
        dis[4][U] = 0, pq.push({0, {4, U}});
    dis[5][U] = 0, pq.push({0, {5, U}});
    while(!pq.empty()) {
        ll d = -pq.top().first;
        int type = pq.top().second.first;
        int v = pq.top().second.second;
        pq.pop();
        if(d != dis[type][v]) continue;
        if(type==2) {
            for(auto [u, w] : g[v]) {
                if(dis[2][u]>d+w)
                    pq.push({-(dis[2][u]=d+w), {2, u}});
                if(dis[0][u]+dis[1][u]==dis[0][T]) {
                    if(dis[3][u]>d+w) pq.push({-(dis[3][u]=d+w), {3, u}});
                    if(dis[4][u]>d+w) pq.push({-(dis[4][u]=d+w), {4, u}});
                }
            }
        }
        else if(type==3) {
            for(auto [u, w] : g[v]) {
                if(dis[0][v]+w+dis[1][u]==dis[0][T] && dis[3][u]>d)
                    pq.push({-(dis[3][u]=d), {3, u}});
                if(dis[5][u]>d+w)
                    pq.push({-(dis[5][u]=d+w), {5, u}});
            }
        }
        else if(type==4) {
            for(auto [u, w] : g[v]) {
                if(dis[1][v]+w+dis[0][u]==dis[0][T] && dis[4][u]>d)
                    pq.push({-(dis[4][u]=d), {4, u}});
                if(dis[5][u]>d+w)
                    pq.push({-(dis[5][u]=d+w), {5, u}});
            }
        }
        else if(type==5) {
            for(auto [u, w] : g[v])
                if(dis[5][u]>d+w)
                    pq.push({-(dis[5][u]=d+w), {5, u}});
        }
    }
    cout << min({dis[3][V], dis[4][V], dis[5][V]}) << '\n';
    return 0;
}

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