제출 #983298

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
983298		farica	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	159 ms	24336 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);
vector<vector<pair<int,int>>>adjL(MAX_N);
vector<pair<int,int>>dp(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 MX, int MY) {
    ans = min(ans, min(MX + D[pos][1], MY + D[pos][0]));
    if(dp[pos].first != -1) return dp[pos];
    int mx = D[pos][0], my = D[pos][1];
    MX = min(MX, mx);
    MY = min(MY, my);
    for(int p: parent[pos]) {
        pair<int,int>cnt = func(p, MX, MY);
        mx = min(mx, cnt.first);
        my = min(my, cnt.second);
    }
    ans = min(ans, min(mx + D[pos][1], my + D[pos][0]));
    ans = min(ans, min(MX + D[pos][1], MY + D[pos][0]));
    return dp[pos] = {mx, my};
}

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);
    ans = D[u][1];
    func(t, D[t][0], D[t][1]);
    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