Submission #810935

#	Time	Username	Problem	Language	Result	Execution time	Memory
810935		winthemcut3	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	258 ms	25968 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 u, vector<ll> &v)
{
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    v.resize(mxN, 1e16);
    v[u]=0;
    pq.push({0, u});
    while (!pq.empty())
    {
        auto [cw, cl]=pq.top();
        pq.pop();
        for (auto [nl, nw]:g[cl])
        {
            if (v[nl]>cw+nw)
            {
                pq.push({cw+nw, nl});
                v[nl]=cw+nw;
            }
        }
    }
}
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; ll 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]);
}
signed 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 dijkstra(int, std::vector<long long int>&)':
commuter_pass.cpp:36:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |         auto [cw, cl]=pq.top();
      |              ^
commuter_pass.cpp:38:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         for (auto [nl, nw]:g[cl])
      |                   ^

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