oj.uz

답안 #482089

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
482089 2021-10-23T03:08:52 Z bill_lin Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 291 ms 26896 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
 
const ll INF = 1e15;

int n;
vector<vector<pii>> adj;
vector<vector<int>> spadj;

vector<ll> dp;
vector<ll> sp, dist_u, dist_v;

ll dfs(int node) {
    if (dp[node] != -1) return dp[node];
    ll best = dist_v[node];
    
    for (int dest : spadj[node]) {
        best = min(best, dfs(dest));
    }
    return dp[node] = best;
}

vector<ll> dijkstra(int start_node) {
    vector<ll> dist(n + 1, INF);
    priority_queue<pll, vector<pll>, greater<pll>> q;
    dist[start_node] = 0;
    q.push({0, start_node});
    
    while (!q.empty()) {
        auto p = q.top();
        q.pop();
        ll curr_cost = p.first, node = p.second;
        for (pii &edge : adj[node]) {
            int dest = edge.first, edge_cost = edge.second;
            if (dist[dest] > curr_cost + edge_cost) {
                dist[dest] = curr_cost + edge_cost;
                q.push({dist[dest], dest});
            }
        }
    }
    
    return dist;
}



int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, S, T, U, V;
    cin >> n >> m >> S >> T >> U >> V;
    
    adj.resize(n + 1);
    spadj.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, cost;
        cin >> u >> v >> cost;
        adj[u].push_back({v, cost});
        adj[v].push_back({u, cost});
    }

    // shortest path, dist to u, dist to v
    sp = dijkstra(S), dist_u = dijkstra(U), dist_v = dijkstra(V);
    vector<bool> vis(n + 1, false);
    // construct the shortest path
    queue<int> q;
    q.push(T);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        ll mn_dist = INF;
        for (pii &edge : adj[node]) {
            mn_dist = min(mn_dist, sp[edge.first]);
        }
        for (pii &edge : adj[node]) {
            int dest = edge.first, edge_cost = edge.second;
            if (sp[dest] + edge_cost == sp[node]) {
                spadj[node].push_back(dest);
                if (!vis[dest]) {
                    vis[dest] = true;
                    q.push(dest);
                }
            }
        }
    }
    
    // dfs from T, calculate, reverse spadj and dfs from S and recalculate
    ll best = dist_v[U];
    dp = vector<ll>(n + 1, -1);
    
    for (int i = 1; i <= n; i++) {
        dfs(i);
        best = min(best, dp[i] + dist_u[i]);
    }
    
    
    vector<vector<int>> tmp(n + 1);
    // reverse the edges
    for (int i = 1; i <= n; i++) {
        for (int j : spadj[i]) {
            tmp[j].push_back(i);
        }
    }
    
    spadj = tmp;
    dp = vector<ll>(n + 1, -1);
    for (int i = 1; i <= n; i++) {
        dfs(i);
        best = min(best, dp[i] + dist_u[i]);
    }
    
    cout << best << '\n';
    
    
    
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 17508 KB Output is correct
2 Correct 226 ms 18892 KB Output is correct
3 Correct 270 ms 22820 KB Output is correct
4 Correct 194 ms 17440 KB Output is correct
5 Correct 229 ms 23668 KB Output is correct
6 Correct 242 ms 21356 KB Output is correct
7 Correct 260 ms 24440 KB Output is correct
8 Correct 251 ms 23900 KB Output is correct
9 Correct 208 ms 21828 KB Output is correct
10 Correct 177 ms 21964 KB Output is correct
11 Correct 94 ms 19892 KB Output is correct
12 Correct 251 ms 21788 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 232 ms 20004 KB Output is correct
2 Correct 251 ms 20044 KB Output is correct
3 Correct 251 ms 19760 KB Output is correct
4 Correct 246 ms 20320 KB Output is correct
5 Correct 247 ms 20396 KB Output is correct
6 Correct 244 ms 23052 KB Output is correct
7 Correct 270 ms 23472 KB Output is correct
8 Correct 251 ms 19680 KB Output is correct
9 Correct 244 ms 20516 KB Output is correct
10 Correct 241 ms 19880 KB Output is correct
11 Correct 100 ms 20808 KB Output is correct
12 Correct 259 ms 23028 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1080 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 11 ms 2380 KB Output is correct
5 Correct 6 ms 1356 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 6 ms 1356 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 17508 KB Output is correct
2 Correct 226 ms 18892 KB Output is correct
3 Correct 270 ms 22820 KB Output is correct
4 Correct 194 ms 17440 KB Output is correct
5 Correct 229 ms 23668 KB Output is correct
6 Correct 242 ms 21356 KB Output is correct
7 Correct 260 ms 24440 KB Output is correct
8 Correct 251 ms 23900 KB Output is correct
9 Correct 208 ms 21828 KB Output is correct
10 Correct 177 ms 21964 KB Output is correct
11 Correct 94 ms 19892 KB Output is correct
12 Correct 251 ms 21788 KB Output is correct
13 Correct 232 ms 20004 KB Output is correct
14 Correct 251 ms 20044 KB Output is correct
15 Correct 251 ms 19760 KB Output is correct
16 Correct 246 ms 20320 KB Output is correct
17 Correct 247 ms 20396 KB Output is correct
18 Correct 244 ms 23052 KB Output is correct
19 Correct 270 ms 23472 KB Output is correct
20 Correct 251 ms 19680 KB Output is correct
21 Correct 244 ms 20516 KB Output is correct
22 Correct 241 ms 19880 KB Output is correct
23 Correct 100 ms 20808 KB Output is correct
24 Correct 259 ms 23028 KB Output is correct
25 Correct 7 ms 1080 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 11 ms 2380 KB Output is correct
29 Correct 6 ms 1356 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 2 ms 460 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 6 ms 1356 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 1 ms 332 KB Output is correct
38 Correct 1 ms 332 KB Output is correct
39 Correct 2 ms 332 KB Output is correct
40 Correct 205 ms 21256 KB Output is correct
41 Correct 207 ms 21704 KB Output is correct
42 Correct 210 ms 21728 KB Output is correct
43 Correct 115 ms 24504 KB Output is correct
44 Correct 127 ms 24932 KB Output is correct
45 Correct 256 ms 26896 KB Output is correct
46 Correct 291 ms 26564 KB Output is correct
47 Correct 199 ms 21188 KB Output is correct
48 Correct 122 ms 22852 KB Output is correct
49 Correct 171 ms 20928 KB Output is correct
50 Correct 237 ms 25500 KB Output is correct
51 Correct 245 ms 26780 KB Output is correct