Submission #810891

#	Time	Username	Problem	Language	Result	Execution time	Memory
810891		winthemcut3	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	182 ms	25012 KiB

commuter_pass

#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define fi   first
#define se   second
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

/** END OF TEMPLATE **/

const int mxN = 1e5 + 5;
struct edge {
    int des; ll c;
};
struct cmp {
    bool operator() (const edge &t1, const edge &t2) {
        return t1.c > t2.c;
    }
};
int n, m, S, T, U, V;
ll ds[mxN], dd[2][mxN], dp[2][mxN];
vector<edge> g[mxN];
void dijkstra(int s, ll d[]) {
    fill(d, d + 1 + n, 1e18);
    priority_queue<edge, vector<edge>, cmp> q;
    q.push({s, 0}); d[s] = 0;
    while(q.size()) {
        int u = q.top().des, du = q.top().c;
        q.pop();
        if(du != d[u]) continue;
        for(edge &v_ : g[u]) {
            int v = v_.des, c = v_.c;
            if(d[v] > d[u] + c) {
                d[v] = d[u] + c;
                q.push({v, d[v]});
            }
        }
    }
}
ll res;
bool vis[mxN];
void dfs(int u) {
    dp[0][u] = dd[0][u];
    dp[1][u] = dd[1][u];
    vis[u] = 1;
    for(edge &v_ : g[u]) {
        int v = v_.des, c = v_.c;
        if(vis[v]) continue;
        if(ds[v] + c != ds[u]) continue;
        dfs(v);
        dp[0][u] = min(dp[0][u], dp[0][v]);
        dp[1][u] = min(dp[1][u], dp[1][v]);
    }
    //cerr << u << ' ' << dp[0][u] << ' ' << dp[1][u] << '\n';
    res = min(res, dp[1][u] + dd[0][u]);
    res = min(res, dp[0][u] + dd[1][u]);
}
int main()
{
    FastIO;
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    cin >> n >> m >> S >> T >> U >> V;
    FOR(i, 1, m) {
        int u, v, c; cin >> u >> v >> c;
        g[u].PB({v, c}); g[v].PB({u, c});
    }
    dijkstra(S, ds);
    dijkstra(U, dd[0]);
    dijkstra(V, dd[1]);

    res = dd[0][V];
    memset(dp, 0x3f, sizeof dp);
    dfs(T);

    cout << res;
    return 0;
}

/*

*/

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