Submission #1111292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111292		injeolmi	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	275 ms	24020 KiB

commuter_pass

#include <bits/stdc++.h>
#define int ll
#define FOR(i,k,n) for(int i = k; i <= n; i++)
#define FORR(i,k,n) for(int i = n; i >= k; i--)
#define pb push_back
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define BIT(S, i) (((S)>>(i))&1)
#define MASK(i) ((1ll)<<(i))
#define name "loopy"
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

template<class X, class Y>
    bool maximize(X &a, Y b) {
        if (a < b) {a = b; return true;}
        return false;
    }

template<class X, class Y>
    bool minimize(X &a, Y b) {
        if (a > b) {a = b; return true;}
        return false;
    }

const int N = 1e5+6;
const int INF = 1e18;
int m, n, s, t, u, v, ans;
vector<pii> adj[N];
vi dist1, dist2, dp1, dp2, d;

void dijkstra(vi &di, int s) {
    di.assign(N, INF);
    di[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    while (q.size()) {
        auto [du, u] = q.top(); q.pop();
        if (du != di[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (di[v] > di[u] + w) {
                di[v] = di[u] + w;
                q.push({di[v], v});
            }
        }
    }
}

int dijkstra2(int s, int t) {
    d.assign(N, INF);
    dp1.assign(N, INF);
    dp2.assign(N, INF);
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    d[s] = 0;
    dp1[s] = dist1[s]; dp2[s] = dist2[s];
    while (q.size()) {
        auto [du, u] = q.top(); q.pop();
        if (du != d[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.push({d[v], v});
                dp1[v] = min(dist1[v], dp1[u]);
                dp2[v] = min(dist2[v], dp2[u]);
            } else if (d[v] == d[u] + w) {
                int minV = min(dp2[u], dist2[v]);
                int minU = min(dp1[u], dist1[v]);
                if (minU + minV <= dp1[v] + dp2[v]) {
                    dp1[v] = minU;
                    dp2[v] = minV;
                }
            }
        }
    }
    return dp1[t] + dp2[t];
}

void solve() {
    FOR(i,0,N-1) adj[i].clear();
    cin >> n >> m >> s >> t >> u >> v;
    while (m--) {
        int x, y, z; cin >> x >> y >> z;
        adj[x].pb({y, z});
        adj[y].pb({x, z});
    }

    dijkstra(dist1, u);
    dijkstra(dist2, v);

    ans = dist1[v];
    minimize(ans, dijkstra2(s,t));
    minimize(ans, dijkstra2(t,s));

    cout << ans << '\n';
}

main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen(name".inp","r")) {
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    solve();
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(vi&, ll)':
commuter_pass.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |         auto [du, u] = q.top(); q.pop();
      |              ^
commuter_pass.cpp:47:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |         for (auto [v, w] : adj[u]) {
      |                   ^
commuter_pass.cpp: In function 'll dijkstra2(ll, ll)':
commuter_pass.cpp:65:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |         auto [du, u] = q.top(); q.pop();
      |              ^
commuter_pass.cpp:67:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |         for (auto [v, w] : adj[u]) {
      |                   ^
commuter_pass.cpp: At global scope:
commuter_pass.cpp:105:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  105 | main(){
      | ^~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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