제출 #594056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
594056		rurutoria7	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	314 ms	21996 KiB

commuter_pass

#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 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45