Submission #810943

#	Time	Username	Problem	Language	Result	Execution time	Memory
810943		winthemcut3	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	188 ms	23964 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;
vector<ll> ds, dd[2];
ll dp[2][mxN];
vector<edge> g[mxN];
void dijkstra(int s, vector<ll> &d) {
    d.resize(n+7, 1e18);
    priority_queue<edge, vector<edge>, cmp> q;
    q.push({s, 0}); d[s] = 0;
    while(q.size()) {
        int u = q.top().des;
        ll du = q.top().c;
        q.pop();
        if(du != d[u]) continue;
        for(edge &v_ : g[u]) {
            int v = v_.des; ll 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)
{
    if (vis[u]) return;
    vis[u]=1;
    dp[0][u]=dd[0][u];
    dp[1][u]=dd[1][u];
    for (auto [nl, nw]:g[u])
    {
        if (ds[nl]+nw==ds[u])
        {
            dfs(nl);
            dp[0][u]=min(dp[0][u], dp[0][nl]);
            dp[1][u]=min(dp[1][u], dp[1][nl]);
        }
    }
    res=min({res, dp[0][u]+dd[1][u], dp[1][u]+dd[0][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;
}

/*

*/

Compilation message (stderr)

commuter_pass.cpp: In function 'void dfs(int)':
commuter_pass.cpp:54:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     for (auto [nl, nw]:g[u])
      |               ^

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