Submission #1038254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038254		Mike_Vu	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	242 ms	33036 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, ll>
#define pb push_back
#define fi first
#define se second

bool maximize(ll &x, ll y ){
    if (x < y) {x = y; return true;};
    return false;
}
bool minimize(ll &x, ll y){
    if (x > y) {x = y; return true;}
    return false;
}

const int maxn = 1e5+5;
int n, m, s1, t1, s2, t2;
vector<pii> a[maxn];
ll ans;

ll dis1[maxn], dis2[maxn], dis3[maxn], dis4[maxn];//dis1 dis2 -> s2 t2
ll dp1[maxn], dp2[maxn];

vector<int> adj[maxn];
int deg[maxn];
bool vis[maxn];

void dijkstra(int s, ll dis[]) {
    priority_queue<pair<ll, int>> q;
    q.push({0, s});
//    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= n; i++) {
        dis[i] = LLONG_MAX;
    }
    dis[s] = 0;
    while (!q.empty()) {
        int u = q.top().se;
        ll w = -q.top().fi;
        q.pop();
        if (w != dis[u]) continue;
//        cout << u << ' ' << dis[u] << "\n";
        for (int i = 0; i < (int)a[u].size(); i++) {
            int v = a[u][i].fi;
            ll w = a[u][i].se;
            if (minimize(dis[v], dis[u]+w)) {
                q.push({-dis[v], v});
            }
        }
    }
}

void dfs1(int u) {
    vis[u] = 1;
    for (int i = 0; i < (int)a[u].size(); i++) {
        int v = a[u][i].fi;
        ll w = a[u][i].se;
        if (dis3[u]+w+dis4[v] == dis3[t1]) {
            adj[u].pb(v);
            deg[v]++;
        }
        if (!vis[v]) dfs1(v);
    }
}

void bfs() {
    queue<int> q;
    q.push(s1);
    memset(dp1, 0x3f, sizeof(dp1));
    memset(dp2, 0x3f, sizeof(dp2));
    while (!q.empty()) {
        int u = q.front(); q.pop();
        minimize(dp1[u], dis1[u]);
        minimize(dp2[u], dis2[u]);
        minimize(ans, min(dp1[u]+dis2[u], dp2[u]+dis1[u]));
//        cout << u << ' ' << dp1[u] << ' ' << dp2[u] << "\n";
        for (int v : adj[u]) {
            deg[v]--;
            minimize(dp1[v], dp1[u]);
            minimize(dp2[v], dp2[u]);
            if (deg[v] == 0) q.push(v);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    cout << "\n";
    cin >> n >> m >> s1 >> t1 >> s2 >> t2;
    for (int i = 1; i <= m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        a[u].pb({v, w});
        a[v].pb({u, w});
    }
    //dijkstra s2->t2
//    system("pause");
    dijkstra(s2, dis1);
    dijkstra(t2, dis2);
//    for (int i = 1; i <= n; i++) {
//        cout << dis1[i] << ' ';
//    }
//    cout << "\n";
    //build dijkstra s1->t1
    dijkstra(s1, dis3);
    dijkstra(t1, dis4);
    ans = dis1[t2];
    //build edges
//    system("pause");
    dfs1(s1);
    //bfs
//    system("pause");
    bfs();
    cout << ans;
}
/*
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
*/

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