Submission #654613

#	Time	Username	Problem	Language	Result	Execution time	Memory
654613		leroycut	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	339 ms	26076 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];
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(us[i.first]) continue;
        if(ds[S] - i.second == ds[i.first]){
            dag[S].push_back(i.first);
            dfs(i.first);
        }
    }
}

ll ans = INF;

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

    // cout << dpv[S] << " " << dpu[S] << " " << S << " !\n";
    ans = min(ans, dpv[S] + dpu[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;
    dfsp(t);

    cout << min(ans, dv[u]);
}

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