Submission #833607

#	Time	Username	Problem	Language	Result	Execution time	Memory
833607		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	268 ms	32292 KiB

commuter_pass

//LaziChicken - 8/2023

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

#define ll long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pli pair <ll, int>
#define pil pair <int, ll>
#define fi first
#define se second
#define dim 3
#define tii tuple <ll, int, int>
#define inf 0x3f

const ll nx = 1e5+2;
const ll bx = 1e3+2;
const ll mod = 1e9+7;

//--------------------------------
int n, m;
ll d[4][nx], dp[2][nx], res = 1e18; //0 S / 1 T / 2 U / 3 V
pii st, en;
bool check[nx];
vector <pli> adj[nx];
vector <tii> edges;
priority_queue <pli, vector<pli>, greater<pli>> pq;

void dijkstra(int dir, int u){
    d[dir][u] = 0; pq.emplace(0, u);
    while(pq.size()){
        ll val;
        tie(val, u) = pq.top();
        pq.pop();
        if (d[dir][u] != val) continue;
        for (auto x : adj[u]){
            ll new_val; int v;
            tie(new_val, v) = x;
            if (d[dir][v] > val + new_val){
                pq.emplace(d[dir][v] = val + new_val, v);
            }
        }
    }
}

void dfs(int u){
    if (check[u]) return;
    check[u] = 1;
    for (auto x : adj[u]){
        ll val; int v;
        tie(val, v) = x;
        dfs(v);
        dp[0][u] = min({dp[0][u], dp[0][v], d[3][v]});
        dp[1][u] = min({dp[1][u], dp[1][v], d[2][v]});
    }
    if (dp[0][u] < 1e18) res = min(res, dp[0][u] + d[2][u]);
    if (dp[1][u] < 1e18) res = min(res, dp[1][u] + d[3][u]); 
}

//--------------------------------
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    cin >> st.fi >> en.fi;
    cin >> st.se >> en.se;
    for (int i = 1, a, b, c; i <= m; i++){
        cin >> a >> b >> c;
        edges.emplace_back(c, a, b);
        edges.emplace_back(c, b, a);
        adj[a].emplace_back(c, b);
        adj[b].emplace_back(c, a);
    }
    memset(d, inf, sizeof(d));
    dijkstra(0, st.fi); dijkstra(1, en.fi);
    dijkstra(2, st.se); dijkstra(3, en.se);
    for (int i = 1; i <= n; i++) adj[i].clear();
    for (auto x : edges){
        ll val; int u, v;
        tie(val, u, v) = x;
        if (d[0][u] + val + d[1][v] != d[0][en.fi]) continue;
        adj[u].emplace_back(val, v);
    }
    memset(dp, inf, sizeof(dp));
    dfs(st.fi);
    cout << min(d[2][en.se], res);
}
/*
Note:

*/

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