Submission #851612

#	Time	Username	Problem	Language	Result	Execution time	Memory
851612		chuongdan	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	231 ms	82328 KiB

commuter_pass

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