Submission #1193919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193919		lidplf	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	798 ms	76620 KiB

commuter_pass

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define MOD2 998244353
using namespace std;
void solve(int cas){
    int n,m; cin>>n>>m;
    int s,t,u,v; cin>>s>>t>>u>>v;--s;--t;--u;--v;
    vector<vector<pair<ll,ll>>> g(n);
    for (int i = 0; i < m; i++){
        ll a,b,c; cin>>a>>b>>c;
        --a;--b;
        g[a].emplace_back(make_pair(b,c));
        g[b].emplace_back(make_pair(a,c));
    }
    vector<ll> ds(n, LLONG_MAX);
    ds[s] = 0;
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> heap;
    vector<set<ll>> par(n);
    heap.push(make_pair(0,s));
    while (!heap.empty()){
        auto [weight, node] = heap.top(); heap.pop();
        if (weight > ds[node]) continue;
        for (auto [neighbor, w]: g[node]){
            if (weight + w < ds[neighbor]){
                ds[neighbor] = weight + w;
                heap.push(make_pair(ds[neighbor], neighbor));
                par[neighbor] = set<ll>{node};
            }
            else if (weight + w == ds[neighbor]){
                par[neighbor].insert(node);
            }
        }
    }
    vector<ll> stk = {t};
    vector<bool> vis(n);
    vis[t] = true;
    set<pair<ll,ll>> edges;
    while (!stk.empty()){
        ll node = stk.back();
        stk.pop_back();
        for (ll x: par[node]){
            edges.insert(make_pair(x, node));
            if (!vis[x]){
                vis[x] = true;
                stk.emplace_back(x);
            }
        }
    }
    set<pair<ll,ll>> rev;
    for (auto& [a, b]: edges) rev.insert(make_pair(b,a));
    vector<vector<vector<ll>>> dp(n, vector<vector<ll>> (3, vector<ll> (2, LLONG_MAX)));
    //0 is not taken, 1 is taking, 2 is done taken
    using tll = tuple<ll,ll,ll,ll>;
    priority_queue<tll, vector<tll>, greater<tll>> heap1; // weight, state, node
    heap1.push(make_tuple(0,0,u,0));
    dp[u][0][0] = 0;
    while (!heap1.empty()){
        auto [weight, state, node, r] = heap1.top(); heap1.pop();
        //cout << weight << " " << state << " " << node + 1 << '\n';
        if (weight > dp[node][state][r]) continue;
        if (node==v){
            cout << weight << '\n';
            return;
        }
        for (auto [neighbor, w]: g[node]){
            if (state==2){
                if (weight + w < dp[neighbor][2][r]){
                    dp[neighbor][2][r] = weight + w;
                    heap1.push(make_tuple(dp[neighbor][2][r], 2, neighbor, r));
                }
            }
            else if (state==1){
                if (weight + w < dp[neighbor][2][r]){
                    dp[neighbor][2][r] = weight + w;
                    heap1.push(make_tuple(dp[neighbor][2][r], 2, neighbor, r));
                }
                if (((!r && edges.count(make_pair(node, neighbor))) || (r && rev.count(make_pair(node, neighbor))))  && weight < dp[neighbor][1][r]){
                    dp[neighbor][1][r] = weight;
                    heap1.push(make_tuple(dp[neighbor][1][r], 1, neighbor, r));
                }
            }
            else{
                if (weight + w < dp[neighbor][0][r]){
                    dp[neighbor][0][r] = weight + w;
                    heap1.push(make_tuple(dp[neighbor][0][r], 0, neighbor, r));
                }
                if (edges.count(make_pair(node, neighbor)) && weight < dp[neighbor][1][0]){
                    dp[neighbor][1][0] = weight;
                    heap1.push(make_tuple(dp[neighbor][1][0], 1, neighbor, 0));
                }
                if (rev.count(make_pair(node, neighbor)) && weight < dp[neighbor][1][1]){
                    dp[neighbor][1][1] = weight;
                    heap1.push(make_tuple(dp[neighbor][1][1], 1, neighbor, 1));
                }
            }
        }
    }
} 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    //cin>>t;
    for (int i = 1; i <= t; i++){
        solve(i);
    }
    return 0;
}

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