Submission #654659

#	Time	Username	Problem	Language	Result	Execution time	Memory
654659		leroycut	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	368 ms	30696 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


const ll INF = 1e18 + 3;
const int N = 1e5 + 3;

class cmt
{
    public:
        bool operator() (pair<int, ll> a, pair<int, ll> b){
            return a.second > b.second;
        }
};

int s, t, v, u, n, m;
vector<pair<int, ll>> g[N];
vector<int> dag[N];
ll dpv[N], dpu[N], ans;
vector<ll> ds, dv, du;
bool us[N];


vector<ll> djikstra(int S){
    vector<ll> d(N, INF);
    d[S] = 0;
    priority_queue<pair<int, ll>, vector<pair<int, ll>>, cmt> q;
    q.push({S, 0});

    while(!q.empty()){
        auto cur = q.top();
        q.pop();
        int node = cur.first;
        ll dist = cur.second;
        if(dist != d[node]) continue;

        for(auto i : g[node]){
            if(dist + i.second < d[i.first]){
                d[i.first] = dist + i.second;
                q.push({i.first, dist + i.second});
            }
        }
    }

    return d;
}

void dfs(int S){
    us[S] = true;
    for(auto i : g[S]){
        if(ds[S] - i.second == ds[i.first]){
            dag[S].push_back(i.first);
            if(!us[i.first]) dfs(i.first);
        }
    }
}

void dfsp(int S){
    us[S] = true;
    dpu[S] = min(dpu[S], du[S]);
    dpv[S] = min(dpv[S], dv[S]);
    for(auto i : dag[S]){
        if(!us[i]) dfsp(i);

        dpu[S] = min(dpu[i], dpu[S]);
        dpv[S] = min(dpv[i], dpv[S]);
    }

    ans = min(ans, dv[S] + dpu[S]);
    ans = min(ans, du[S] + dpv[S]);
}

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

    for(int i = 0; i < N; ++i){
        dpu[i] = dpv[i] = INF;
    }

    cin >> n >> m >> s >> t >> v >> u;

    for(int i = 0; i < m; ++i){
        int a, b;
        ll c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    ds = djikstra(s);
    du = djikstra(u);
    dv = djikstra(v);
    dfs(t);
    for(int i = 0; i < N; ++i) us[i] = false;
    ans = dv[u];
    dfsp(t);

    // for(int i = 1; i <= n; ++i){
    //     cout << i << " ! ";
    //     for(auto j : dag[i]){
    //         cout << j << " ";
    //     }
    //     cout << "\n";
    // }
    
    cout << ans;
}

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