Submission #811097

#	Time	Username	Problem	Language	Result	Execution time	Memory
811097		boyliguanhan	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	202 ms	29252 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int, int>> adj[200100];
int dist[3][200100], dp[2][200100];
bitset<200100> vis;
void djikstra(int start, int ind) {
    memset(dist[ind], 15, sizeof dist[ind]);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0,start});
    dist[ind][start] = 0;
    while(pq.size()) {
        int x = pq.top().second, y = dist[ind][x];
        pq.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(auto [to,weight]: adj[x])
            if(y+weight < dist[ind][to])
                pq.push({dist[ind][to]=y+weight,to});
    }
    vis.reset();
}
int ans;
void dfs(int n) {
    vis[n] = 1;
    dp[0][n] = dist[0][n];
    dp[1][n] = dist[1][n];
    for (auto [to, weight]: adj[n]) {
        if (dist[2][n] - weight != dist[2][to]) continue;
        if (!vis[to]) dfs(to);
        dp[0][n] = min(dp[0][n], dp[0][to]);
        dp[1][n] = min(dp[1][n], dp[1][to]);
    }
    ans = min(ans, min(dp[0][n] + dist[1][n], dp[1][n] + dist[0][n]));
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    djikstra(u,0);
    djikstra(v,1);
    djikstra(s,2);
    ans = dist[0][v];
    dfs(t);
    cout << ans << '\n';
}

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