Submission #1087581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087581		pqthangv	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	181 ms	23236 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 1e9 + 5;
const ll oo = 1e18 + 5;

const int MAXN = 1e5 + 5;

#define int ll

int n, m, s, t, u, v, dist[MAXN][3], best[MAXN][2];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int> > > pq;
vector<pair<int, int>> adj[MAXN];
bool vis[MAXN];
int ans;

void DJ(int source, int type) {
    for (int i = 1; i <= n; ++i) dist[i][type] = oo;
    pq.push({0, source});
    dist[source][type] = 0;

    while (!pq.empty()) {
        pair<int, int> t = pq.top(); pq.pop();
        int u = t.second, kcu = t.first;

        if (kcu > dist[u][type]) continue;

        for (int i = 0; i < int(adj[u].size()); ++i) {
            int v = adj[u][i].first, kcv = adj[u][i].second;

            if (dist[v][type] > dist[u
                ][type] + kcv) {
                dist[v][type] = dist[u][type] + kcv;
                pq.push({dist[v][type], v});
            }
        }
    }
}

void DFS(int u) {
    best[u][0] = dist[u][1];
    best[u][1] = dist[u][2];
//    cout << u << ' ';
    vis[u] = true;
    for (int i = 0; i < int(adj[u].size()); ++i){
        int v = adj[u][i].first, kcv = adj[u][i].second;
        if (dist[v][0] == dist[u][0] - kcv) {
            if (!vis[v]) DFS(v);
            best[u][0] = min(best[u][0], best[v][0]);
            best[u][1] = min(best[u][1], best[v][1]);
        }
    }
    ans = min(ans, dist[u][1] + best[u][1]);
    ans = min(ans, dist[u][2] + best[u][0]);
}


void solve() {
    cin >> n >> m >> s >> t >> u >> v;

    for (int i = 1; i <= m; ++i) {
        int u, v, w; cin >> u >> v >> w;

        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }


    DJ(s, 0);
    DJ(u, 1);
    DJ(v, 2);

    ans = dist[v][1];
    DFS(t);
//
//    cout << dist[3][0] << ' ';
//
    cout << ans;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

//    int T = 1; cin >> T; while(T--)
    solve();

    return 0;
}

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