oj.uz

Submission #594056

# Submission time Handle Problem Language Result Execution time Memory
594056 2022-07-12T03:00:56 Z rurutoria7 Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 314 ms 21996 KB 
#include <bits/stdc++.h>
#define int long long
#define rep(i,j,k) for (int i=j; i<=k; i++)
#define de(x) cout << #x << "=" << x << ", "
#define dd cout << '\n';
#define ff first
#define ss second
#define pb push_back
#define lyx_my_wife ios::sync_with_stdio(0), cin.tie(0);
using namespace std;
typedef pair<int,int> pii;

const int N = 1e5+10, M = 2e5+10;

int n, m, s, t, u, v;
vector<pii> G[N];

int disu[N], disv[N], diss[N], dist[N], vis[N];
int dpu[N], dpv[N], ans;

void dijks(int rt, int dis[N], int fordp=0, int forans=0)
{
    memset(dis, 0x3f, sizeof(disu));
    memset(vis, 0, sizeof(vis));
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dis[rt] = 0;
    pq.push({0, rt});

    if (fordp)
    {
        memset(dpu, 0x3f, sizeof(dpu));
        memset(dpv, 0x3f, sizeof(dpv));
    }
    
    while(pq.size())
    {
        int i = pq.top().ss, d = pq.top().ff;
        pq.pop(); 

        if (vis[i]) continue;
        vis[i] = 1;

        if (fordp)
        {
            dpu[i] = min(dpu[i], disu[i]);
            dpv[i] = min(dpv[i], disv[i]);            
        }

        for (auto e: G[i])
        {
            int j = e.ss, w = e.ff;

            if (forans)
            {
                if (diss[j] != diss[i]-w) continue;
                ans = min(ans, dpu[j]+disv[i]);
                ans = min(ans, dpv[j]+disu[i]);
            }

            if (dis[j] > d+w)
            {
                dis[j] = d+w;
                pq.push({dis[j], j});
                if (fordp) dpu[j] = dpu[i], dpv[j] = dpv[i];
            }
            else if (dis[j] == d+w)
            {
                if (fordp) dpu[j] = min(dpu[j], dpu[i]), dpv[j] = min(dpv[j], dpv[i]);
            }
        }
    }
}

signed main()
{
    lyx_my_wife
    cin >> n >> m >> s >> t >> u >> v;
    rep(_,1,m)
    {
        int i, j, w;
        cin >> i >> j >> w;
        G[i].pb({w,j});
        G[j].pb({w,i});
    }

    // dijks for disu, disv
    dijks(u,disu);
    dijks(v,disv);
    dijks(s,diss,1);
    ans = disu[v];
    dijks(t,dist,0,1);
    cout << ans << '\n';
}
/*
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1

6 5
1 2
3 6
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10

8 8
5 7
6 8
1 2 2
2 3 3
3 4 4
1 4 1 
1 5 5 
2 6 6 
3 7 7 
4 8 8

5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10
*/

/*
> 無向圖，選一條 s-t 最短路使其邊權歸零，使 u-v 路徑最短

將無向圖拆成有向圖，從 s 開始的最短路徑有一個 DAG as sDAG
s->t最短路也有 DAG 屬於 sDAG as stDAG

! stDAG 的任何一條 st 路徑都是合法的最短路
! stDAG inverse as tsDAG 的任何一條 ts 路徑都是合法的最短路

from u to v in stDAG
from v to u in stDAG

! u -> (x -> y)stDAG -> v
! sv -> (x -> y)stDAG -> u

! ans = min(dis[u][x] + dis[y][v])
! ans = min(dis[v][x] + dis[y][u])

! ans = min(dis[u][x] + dis[v][y])
! ans = min(dis[v][x] + dis[u][y])
+ dpu: on stDAG, min dis[u][x]
+ dpv: on stDAG, min dis[v][x]
+ ans = min(ans, dpu + disv[i])
+ ans = min(ans, dpv + disu[i])
*/

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 21984 KB Output is correct
2 Correct 243 ms 20764 KB Output is correct
3 Correct 314 ms 20356 KB Output is correct
4 Correct 230 ms 21448 KB Output is correct
5 Correct 263 ms 20400 KB Output is correct
6 Correct 255 ms 21996 KB Output is correct
7 Correct 299 ms 20588 KB Output is correct
8 Correct 278 ms 20736 KB Output is correct
9 Correct 246 ms 20532 KB Output is correct
10 Correct 222 ms 20412 KB Output is correct
11 Correct 138 ms 14416 KB Output is correct
12 Correct 290 ms 20472 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 20840 KB Output is correct
2 Correct 291 ms 20588 KB Output is correct
3 Correct 301 ms 20640 KB Output is correct
4 Correct 277 ms 20692 KB Output is correct
5 Correct 299 ms 20676 KB Output is correct
6 Correct 288 ms 20432 KB Output is correct
7 Correct 286 ms 20564 KB Output is correct
8 Correct 299 ms 20856 KB Output is correct
9 Correct 269 ms 20608 KB Output is correct
10 Correct 289 ms 20608 KB Output is correct
11 Correct 119 ms 14352 KB Output is correct
12 Correct 296 ms 20404 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9820 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 5 ms 8156 KB Output is correct
4 Correct 19 ms 11604 KB Output is correct
5 Correct 12 ms 9812 KB Output is correct
6 Correct 5 ms 8196 KB Output is correct
7 Correct 7 ms 8328 KB Output is correct
8 Correct 6 ms 8404 KB Output is correct
9 Correct 5 ms 8276 KB Output is correct
10 Correct 11 ms 9812 KB Output is correct
11 Correct 4 ms 8056 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 4 ms 8196 KB Output is correct
15 Correct 4 ms 8148 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 21984 KB Output is correct
2 Correct 243 ms 20764 KB Output is correct
3 Correct 314 ms 20356 KB Output is correct
4 Correct 230 ms 21448 KB Output is correct
5 Correct 263 ms 20400 KB Output is correct
6 Correct 255 ms 21996 KB Output is correct
7 Correct 299 ms 20588 KB Output is correct
8 Correct 278 ms 20736 KB Output is correct
9 Correct 246 ms 20532 KB Output is correct
10 Correct 222 ms 20412 KB Output is correct
11 Correct 138 ms 14416 KB Output is correct
12 Correct 290 ms 20472 KB Output is correct
13 Correct 294 ms 20840 KB Output is correct
14 Correct 291 ms 20588 KB Output is correct
15 Correct 301 ms 20640 KB Output is correct
16 Correct 277 ms 20692 KB Output is correct
17 Correct 299 ms 20676 KB Output is correct
18 Correct 288 ms 20432 KB Output is correct
19 Correct 286 ms 20564 KB Output is correct
20 Correct 299 ms 20856 KB Output is correct
21 Correct 269 ms 20608 KB Output is correct
22 Correct 289 ms 20608 KB Output is correct
23 Correct 119 ms 14352 KB Output is correct
24 Correct 296 ms 20404 KB Output is correct
25 Correct 11 ms 9820 KB Output is correct
26 Correct 4 ms 8148 KB Output is correct
27 Correct 5 ms 8156 KB Output is correct
28 Correct 19 ms 11604 KB Output is correct
29 Correct 12 ms 9812 KB Output is correct
30 Correct 5 ms 8196 KB Output is correct
31 Correct 7 ms 8328 KB Output is correct
32 Correct 6 ms 8404 KB Output is correct
33 Correct 5 ms 8276 KB Output is correct
34 Correct 11 ms 9812 KB Output is correct
35 Correct 4 ms 8056 KB Output is correct
36 Correct 4 ms 8148 KB Output is correct
37 Correct 4 ms 8148 KB Output is correct
38 Correct 4 ms 8196 KB Output is correct
39 Correct 4 ms 8148 KB Output is correct
40 Correct 256 ms 21580 KB Output is correct
41 Correct 254 ms 20580 KB Output is correct
42 Correct 271 ms 20796 KB Output is correct
43 Correct 118 ms 14408 KB Output is correct
44 Correct 128 ms 14384 KB Output is correct
45 Correct 266 ms 21068 KB Output is correct
46 Correct 277 ms 20976 KB Output is correct
47 Correct 237 ms 21256 KB Output is correct
48 Correct 138 ms 14352 KB Output is correct
49 Correct 239 ms 21412 KB Output is correct
50 Correct 265 ms 20424 KB Output is correct
51 Correct 308 ms 21136 KB Output is correct