Submission #983405

#	Time	Username	Problem	Language	Result	Execution time	Memory
983405		farica	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	187 ms	30416 KiB

commuter_pass

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

using namespace std;

const int MAX_N = 100005;

int n, s, t, u, v, D[MAX_N][2], ans;
vector<vector<int>>parent(MAX_N), children(MAX_N);
vector<vector<pair<int,int>>>adjL(MAX_N);
vector<pair<int,int>>dp(MAX_N), dp2(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, int type) {
    if(!type && dp[pos].first != -1) return dp[pos];
    else if(type && dp2[pos].first != -1) return dp2[pos];
    dp[pos].first = dp2[pos].first = D[pos][0];
    dp[pos].second = dp2[pos].second = D[pos][1];
    if(!type) {
        for(int p: parent[pos]) {
            pair<int,int>cnt = func(p, type);
            if(min(cnt.first, D[pos][0]) + min(cnt.second, D[pos][1]) <= dp[pos].first + dp[pos].second) {
                dp[pos].first = min(cnt.first, D[pos][0]);
                dp[pos].second = min(cnt.second, D[pos][1]);
            }
        }
    } else {
        for(int p: children[pos]) {
            pair<int,int>cnt = func(p, type);
            if(min(cnt.first, D[pos][0]) + min(cnt.second, D[pos][1]) <= dp2[pos].first + dp2[pos].second) {
                dp2[pos].first = min(cnt.first, D[pos][0]);
                dp2[pos].second = min(cnt.second, D[pos][1]);
            }
        }
    }
    if(!type) return dp[pos];
    else return dp2[pos];
}

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;
                children[cur].push_back(adj.first);
                parent[adj.first].push_back(cur);
            } else if(w == d[adj.first]) {
                parent[adj.first].push_back(cur);
                children[cur].push_back(adj.first);
            }
        }
    }
    for(int i=0; i<n; ++i) dp[i] = dp2[i] = {-1, -1};
    calc(u, 0);
    calc(v, 1);
    ans = D[u][1];
    func(t, 0);
    func(s, 1);
    ans = min(ans, min(dp[t].first + dp[t].second, dp2[s].first + dp2[s].second));
    cout << ans << 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