Submission #680385

#	Time	Username	Problem	Language	Result	Execution time	Memory
680385		_martynas	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	305 ms	24196 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int MXN = 1e5+5;
const ll INF = 1e15;

int n, m;
int s, t, u, v;
vector<pii> adj[MXN];
vector<pii> dag[MXN]; // s -> t
ll dist_s[MXN], dist_t[MXN];
ll dist_u[MXN], dist_v[MXN];

void dijkstra(int start, ll dist[]) {
    priority_queue<pli, vector<pli>, greater<pli>> PQ;
    fill(dist, dist+n+1, INF);
    dist[start] = 0;
    PQ.push({0, start});
    while(!PQ.empty()) {
        ll d = PQ.top().F;
        int i = PQ.top().S;
        PQ.pop();
        if(d != dist[i]) continue;
        for(auto e : adj[i]) {
            if(dist[e.F] > d+e.S) {
                dist[e.F] = d+e.S;
                PQ.push({dist[e.F], e.F});
            }
        }
    }
}

bool visited[MXN];
pll mn[MXN]; // first - min dist to v, second - min dist to u
ll ans = INF;
void recur(int i) {
    if(visited[i]) return;
    visited[i] = true;
    mn[i].F = dist_v[i];
    mn[i].S = dist_u[i];
    for(auto e : dag[i]) {
        recur(e.F);
        mn[i].F = min(mn[i].F, mn[e.F].F);
        mn[i].S = min(mn[i].S, mn[e.F].S);
    }
    ans = min(ans, dist_u[i]+mn[i].F);
    ans = min(ans, dist_v[i]+mn[i].S);
}

int main() {
    FASTIO();
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    for(int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].PB({b, c});
        adj[b].PB({a, c});
    }
    dijkstra(s, dist_s);
    dijkstra(t, dist_t);
    dijkstra(u, dist_u);
    dijkstra(v, dist_v);
    for(int i = 1; i <= n; i++) {
        for(auto e : adj[i]) {
            if(dist_s[i]+dist_t[e.F]+e.S == dist_s[t]) {
                dag[i].PB(e);
            }
        }
    }
    ans = dist_u[v];
    for(int i = 1; i <= n; i++) {
        if(!dag[i].empty()) {
            recur(i);
        }
    }
    cout << ans << "\n";
    return 0;
}

/*
6 6
1 5
4 6
1 2 1
2 3 1
3 5 1
2 4 2
4 5 3
5 6 1
ans: 3

7 9
1 5
4 6
7 2 1
7 3 1
7 5 1
1 2 1
2 3 1
3 5 1
2 4 2
4 5 3
5 6 1
ans: 3

5 5
1 3
4 5
1 2 1
2 3 1
1 3 2
1 4 3
2 5 3
ans: 6

5 6
1 3
4 5
1 2 1
2 3 1
1 3 2
1 4 3
2 5 3
3 5 1
ans: 4

*/

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45