Submission #854408

#	Time	Username	Problem	Language	Result	Execution time	Memory
854408		_callmelucian	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	310 ms	36516 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pl;
typedef tuple<int,int,int> tt;
#define all(v) v.begin(), v.end()

const int mn = 1e5 + 10;
ll dist[4][mn], dp[mn];
vector<pl> adj[mn], subg[mn];
bool vis[mn];
int n, node;

void dijkstra (int save, int source) {
    for (int i = 1; i <= n; i++) vis[i] = 0, dist[save][i] = LLONG_MAX;
    dist[save][source] = 0;
    priority_queue<pl> pq;
    pq.push({0, source});
    while (pq.size()) {
        int a = pq.top().second; pq.pop();
        if (vis[a]) continue;
        vis[a] = 1;
        for (pl it : adj[a]) {
            ll w; int b; tie(w, b) = it;
            if (dist[save][a] + w < dist[save][b]) {
                dist[save][b] = dist[save][a] + w;
                pq.push({-dist[save][b], b});
            }
        }
    }
    return;
}

void addEdge (int a, int b, ll c) {
    subg[a].push_back({c, b});
}

ll finalD() {
    for (int i = 0; i <= node; i++) vis[i] = 0, dp[i] = LLONG_MAX;
    dp[0] = 0;
    priority_queue<pl> pq;
    pq.push({0, 0});
    while (pq.size()) {
        int a = pq.top().second; pq.pop();
        if (vis[a]) continue;
        vis[a] = 1;
        for (pl it : subg[a]) {
            ll w; int b; tie(w, b) = it;
            if (dp[a] + w < dp[b]) {
                dp[b] = dp[a] + w;
                pq.push({-dp[b], b});
            }
        }
    }
    return dp[node];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int m; cin >> n >> m;
    int s, t, u, v; cin >> s >> t >> u >> v;
    node = n + 1;

    vector<tt> edge(m);
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].push_back({c, b});
        adj[b].push_back({c, a});
        edge[i] = make_tuple(a, b, c);
    }

    dijkstra(0, s);
    dijkstra(1, t);
    dijkstra(2, u);
    dijkstra(3, v);

    ll ans = dist[2][v];

    for (int i = 1; i <= n; i++) {
        if (dist[0][i] + dist[1][i] > dist[0][t]) continue;
        addEdge(0, i, dist[2][i]);
        addEdge(i, node, dist[3][i]);
    }
    for (int i = 0; i < m; i++) {
        int a, b; ll c; tie(a, b, c) = edge[i];
        if (dist[0][a] + c + dist[1][b] == dist[0][t]) addEdge(a, b, 0);
        if (dist[0][b] + c + dist[1][a] == dist[0][t]) addEdge(b, a, 0);
    }
    ans = min(ans, finalD());

    for (int i = 0; i <= node; i++) subg[i].clear();
    for (int i = 1; i <= n; i++) {
        if (dist[0][i] + dist[1][i] > dist[0][t]) continue;
        addEdge(0, i, dist[2][i]);
        addEdge(i, node, dist[3][i]);
    }
    for (int i = 0; i < m; i++) {
        int a, b; ll c; tie(a, b, c) = edge[i];
        if (dist[0][a] + c + dist[1][b] == dist[0][t]) addEdge(b, a, 0);
        if (dist[0][b] + c + dist[1][a] == dist[0][t]) addEdge(a, b, 0);
    }
    ans = min(ans, finalD());

    cout << ans;

    return 0;
}

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