oj.uz

답안 #851612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
851612 2023-09-20T09:10:58 Z chuongdan Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 231 ms 82328 KB 
#include <bits/stdc++.h>
#define N 1000000
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define reprev(i, l, r) for(int i = l; i >= r; i--)

using namespace std;

typedef pair<int,int> i2;
typedef pair<i2,int> i3;
typedef pair<i2, i2> i4;

const int INF = 1e18;
const int MOD = 1e9 + 7;

int n, m, s, t, x, y;
int dp[N+5][2], dpu[N+5];
i3 edge[N+5];
vector<i2> g[N+5], g2[N+5];

void dijkstra(int start, int oper){
    rep(i, 1, n) dp[i][oper] = INF;
    priority_queue<i2, vector<i2>, greater<i2>> heap;
    dp[start][oper] = 0;
    heap.push(mp(0, start));
    while (heap.size()){
        i2 cur = heap.top(); heap.pop();
        if (cur.fi > dp[cur.se][oper]) continue;
        int u = cur.se;
        for(auto p: g[u]){
            int v = p.fi, w = p.se;
            if (dp[v][oper] > cur.fi + w){
                dp[v][oper] = cur.fi + w;
                heap.push(mp(dp[v][oper], v));
            }
        }
    }
}

void dijkstra_u(){
    rep(i, 1, n) dpu[i] = INF;
    priority_queue<i2, vector<i2>, greater<i2>> heap;
    dpu[x] = 0;
    heap.push(mp(0, x));
    while (heap.size()){
        i2 cur = heap.top(); heap.pop();
        if (cur.fi > dpu[cur.se]) continue;
        int u = cur.se;
        for(auto p: g2[u]){
            int v = p.fi, w = p.se;
            if (dpu[v] > cur.fi + w){
                dpu[v] = cur.fi + w;
                heap.push(mp(dpu[v], v));
            }
        }
    }
}

void solve(){
    cin >> n >> m >> s >> t >> x >> y;
    rep(i, 1, m) {
        cin >> edge[i].fi.fi >> edge[i].fi.se >> edge[i].se;
        g[edge[i].fi.fi].pb(mp(edge[i].fi.se, edge[i].se));
        g[edge[i].fi.se].pb(mp(edge[i].fi.fi, edge[i].se));
    }
    dijkstra(s, 0);
    dijkstra(t, 1);
    rep(i, 1, m){
        int u = edge[i].fi.fi, v = edge[i].fi.se, w = edge[i].se;
        if (dp[u][0] + dp[v][1] + w == dp[t][0] || dp[u][1] + dp[v][0] + w == dp[t][0]){
            g2[u].pb({v, 0});
            g2[v].pb({u, 0});
        } else {
            g2[u].pb({v, w});
            g2[v].pb({u, w});
        }
    }
    dijkstra_u();
    cout << dpu[y];
}  

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 81340 KB Output is correct
2 Correct 203 ms 80272 KB Output is correct
3 Correct 231 ms 80300 KB Output is correct
4 Correct 184 ms 80068 KB Output is correct
5 Correct 183 ms 79996 KB Output is correct
6 Correct 220 ms 81316 KB Output is correct
7 Correct 188 ms 79968 KB Output is correct
8 Correct 194 ms 80268 KB Output is correct
9 Correct 225 ms 79956 KB Output is correct
10 Correct 173 ms 79652 KB Output is correct
11 Correct 81 ms 64084 KB Output is correct
12 Correct 209 ms 79964 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 81308 KB Output is correct
2 Correct 203 ms 80264 KB Output is correct
3 Correct 209 ms 81280 KB Output is correct
4 Correct 196 ms 80256 KB Output is correct
5 Correct 217 ms 82328 KB Output is correct
6 Correct 205 ms 82164 KB Output is correct
7 Correct 203 ms 81276 KB Output is correct
8 Correct 206 ms 80260 KB Output is correct
9 Correct 210 ms 81300 KB Output is correct
10 Correct 197 ms 80252 KB Output is correct
11 Correct 79 ms 64080 KB Output is correct
12 Correct 207 ms 80356 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 56408 KB Output is correct
2 Correct 12 ms 51800 KB Output is correct
3 Incorrect 11 ms 51800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 81340 KB Output is correct
2 Correct 203 ms 80272 KB Output is correct
3 Correct 231 ms 80300 KB Output is correct
4 Correct 184 ms 80068 KB Output is correct
5 Correct 183 ms 79996 KB Output is correct
6 Correct 220 ms 81316 KB Output is correct
7 Correct 188 ms 79968 KB Output is correct
8 Correct 194 ms 80268 KB Output is correct
9 Correct 225 ms 79956 KB Output is correct
10 Correct 173 ms 79652 KB Output is correct
11 Correct 81 ms 64084 KB Output is correct
12 Correct 209 ms 79964 KB Output is correct
13 Correct 215 ms 81308 KB Output is correct
14 Correct 203 ms 80264 KB Output is correct
15 Correct 209 ms 81280 KB Output is correct
16 Correct 196 ms 80256 KB Output is correct
17 Correct 217 ms 82328 KB Output is correct
18 Correct 205 ms 82164 KB Output is correct
19 Correct 203 ms 81276 KB Output is correct
20 Correct 206 ms 80260 KB Output is correct
21 Correct 210 ms 81300 KB Output is correct
22 Correct 197 ms 80252 KB Output is correct
23 Correct 79 ms 64080 KB Output is correct
24 Correct 207 ms 80356 KB Output is correct
25 Correct 17 ms 56408 KB Output is correct
26 Correct 12 ms 51800 KB Output is correct
27 Incorrect 11 ms 51800 KB Output isn't correct
28 Halted 0 ms 0 KB -