Submission #854728

#	Time	Username	Problem	Language	Result	Execution time	Memory
854728		lmToT27	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	385 ms	38296 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
long long dp[100005][5], dist[100005];
vector <pair <int, int>> ke[100005];
pair <long long, long long> f[100005][5];
long long ans = LLONG_MAX;
int n, m, s[5];
struct lmt {
    long long cost, sub;
    int u, type;
    bool operator < (const lmt other) const {
        if (cost != other.cost)
            return cost > other.cost;
        return sub > other.sub;
    }
};
priority_queue <lmt> qz;
void dijkstra(int id) {
    for (int i = 1; i <= n; i++)
        dist[i] = LLONG_MAX;
    dist[s[id]] = 0;
    priority_queue <pair <long long, int>, vector <pair <long long, int>>, greater <pair <long long, int>>> q;
    q.push({0, s[id]});
    while (q.size()) {
        long long now = q.top().first;
        int u = q.top().second;
        q.pop();
        if (dist[u] != now)
            continue;
        for (pair <int, int> next : ke[u]) {
            int v = next.first;
            int w = next.second;
            if (dist[v] > now + w) {
                dist[v] = now + w;
                q.push({dist[v], v});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        dp[i][id - 2] = dist[i];
        dp[i][2] += dist[i];
    }
    ans = dist[s[id ^ 1]];
}
void solve() {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 2; j++)
            f[i][j] = {LLONG_MAX, dp[i][j]};
    }
    for (int j = 0; j <= 2; j++) {
        f[s[0]][j] = {0, dp[s[0]][j]};
        qz.push({0, dp[s[0]][j], s[0], j});
    }
    while (qz.size()) {
        long long val = qz.top().cost;
        long long to = qz.top().sub;
        int u = qz.top().u;
        int type = qz.top().type;
        qz.pop();
        if (f[u][type].first != val || f[u][type].second != to)
            continue;
        for (pair <int, int> next : ke[u]) {
            int v = next.first;
            int w = next.second;
            if (val + w < f[v][type].first) {
                f[v][type].first = val + w;
                f[v][type].second = min(dp[v][type], f[u][type].second);
                qz.push({f[v][type].first, f[v][type].second, v, type});
            } else if (val + w == f[v][type].first) {
                if (f[u][type].second < f[v][type].second) {
                    f[v][type].second = f[u][type].second;
                    qz.push({f[v][type].first, f[v][type].second, v, type});
                }
            }
            if (type != 2) {
                if (val + w < f[v][2].first) {
                    f[v][2].first = val + w;
                    f[v][2].second = f[u][type].second + min(dp[v][type ^ 1], dp[u][type ^ 1]);
                    qz.push({f[v][2].first, f[v][2].second, v, 2});
                } else if (val + w == f[v][2].first) {
                    if (f[u][type].second + min(dp[v][type ^ 1], dp[u][type ^ 1]) < f[v][2].second) {
                        f[v][type].second = f[u][type].second + min(dp[v][type ^ 1], dp[u][type ^ 1]);
                        qz.push({f[v][type].first, f[v][type].second, v, type});
                    }
                }
            }
        }
    }
    ans = min(ans, f[s[1]][2].second);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    freopen("TASK.INP", "r", stdin);
//    freopen("TASK.OUT", "w", stdout);
    cin >> n >> m;
    for (int i = 0; i <= 3; i++)
        cin >> s[i];
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        ke[u].push_back({v, c});
        ke[v].push_back({u, c});
    }
    dijkstra(2);
    dijkstra(3);
    solve();
    cout << ans;
    return 0;
}

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