Submission #983069

#	Time	Username	Problem	Language	Result	Execution time	Memory
983069		farica	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	186 ms	29712 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAX_N = 100000;

int n, s, t, u, v, D[MAX_N][2];
vector<vector<int>>parent(MAX_N);
vector<pair<int,int>>dp(MAX_N), M(MAX_N);
vector<vector<pair<int,int>>>adjL(MAX_N);

void calc(int x, int type) {
    priority_queue<pair<int,int>>pq;
    pq.push({0, x});
    for(int i=0; i<n; ++i) D[i][type] = -1;
    D[x][type] = 0;
    while(!pq.empty()) {
        int cur = pq.top().second;
        pq.pop();
        for(pair<int,int>adj: adjL[cur]) {
            int w = adj.second + D[cur][type];
            if(D[adj.first][type] == -1) {
                D[adj.first][type] = w;
                pq.push({-w, adj.first});
            }
        }
    }
}

pair<int,int> func(int pos) {
    if(dp[pos].first != -1) return dp[pos];
    dp[pos].first = M[pos].first = D[pos][0];
    dp[pos].second = M[pos].second = D[pos][1];
    for(int p: parent[pos]) {
        pair<int,int>cnt = func(p);
        M[pos].first = min(M[pos].first, M[p].first);
        M[pos].second = min(M[pos].second, M[p].second);
        if(cnt.first + cnt.second < dp[pos].first + dp[pos].second) dp[pos].first = cnt.first, dp[pos].second = cnt.second;
    }
    int X = M[pos].first + D[pos][1], Y = M[pos].second + D[pos][0];
    if(X < Y && X < dp[pos].first + dp[pos].second) dp[pos].first = M[pos].first, dp[pos].second = D[pos][1];
    else if(Y < dp[pos].first + dp[pos].second) dp[pos].second = M[pos].second, dp[pos].first = D[pos][0];
    return {0, M[pos].second};
}

void solve() {
    int m;
    cin >> n >> m >> s >> t >> u >> v;
    --s, --t, --u, --v;
    for(int i=0; i<m; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        --a, --b;
        adjL[a].push_back({b, w});
        adjL[b].push_back({a, w});
    }
    for(int i=0; i<n; ++i) dp[i] = {-1, -1};
    priority_queue<pair<int,int>>pq;
    pq.push({0, s});
    vector<int>d(n, -1);
    d[s] = 0;
    while(!pq.empty()) {
        int dist = -pq.top().first, cur = pq.top().second;
        pq.pop();
        for(pair<int,int>adj: adjL[cur]) {
            int w = dist + adj.second;
            if(d[adj.first] == -1) {
                pq.push({-w, adj.first});
                d[adj.first] = w;
                parent[adj.first].push_back(cur);
            } else if(w == d[adj.first]) parent[adj.first].push_back(cur);
        }
    }
    calc(u, 0);
    calc(v, 1);
    func(t);
    cout << min(dp[t].first + dp[t].second, min(D[u][1], D[v][0])) << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("shortcut.in", "r", stdin);
    //freopen("shortcut.out", "w", stdout);

    int t=1;
    while(t--) solve();

    return 0;
}

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