Submission #1124515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124515		seoul_korea	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	409 ms	27384 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
#define int long long
using ii = pair<int, int>;
#define F first
#define S second
#define REP(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; }
template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; }

mt19937 rng(time(0));

const int N = (int)1e5 + 7, INF = (int)7e18;
vector<ii> adj[N];
int dp[N][2];
int du[N], dv[N], d[N];
bool vis[N];
int n, m, s, t, l, r;

void Precompute(int start, int dist[])
{
    priority_queue<ii> pq;
    dist[start] = 0;
    pq.push({0, start});
    while(pq.size())
    {
        int u, f;
        tie(f, u) = pq.top();
        pq.pop();
        f = -f;
        if(dist[u] != f)
            continue;
        for(ii nxt : adj[u])
        {
            int v, w;
            tie(v, w) = nxt;
            if(minimize(dist[v], f + w))
                pq.push({-dist[v], v});
        }
    }
}

int ans;

void Calc(int st, int en)
{
    priority_queue<array<int, 3>> pq;
    memset(dp, 0x3f, sizeof dp);
    memset(vis, 0, sizeof vis);
    fill(d, d + n + 1, INF);
    d[st] = 0;
    pq.push({0, st, 0});
    while(pq.size())
    {
        int f, u, par;
        array<int, 3> TOP = pq.top();
        f = TOP[0];
        u = TOP[1];
        par = TOP[2];
        pq.pop();
        if(!vis[u])
        {
            vis[u] = 1;
            d[u] = -f;
            dp[u][0] = min(dp[par][0], du[u]);
            dp[u][1] = min(dp[par][1], dv[u]);
            for(ii nxt : adj[u])
            {
                int v, w;
                tie(v, w) = nxt;
                pq.push({f - w, v, u});
            }
        }else if(-f == d[u])
        {
            int f1 = min(dp[par][0], du[u]);
            int f2 = min(dp[par][1], dv[u]);
            if(f1 + f2 <= dp[u][0] + dp[u][1])
            {
                dp[u][0] = f1;
                dp[u][1] = f2;
            }
        }

    }
    minimize(ans, dp[en][0] + dp[en][1]);
}

signed main(void)
{
    cin.tie(nullptr)->sync_with_stdio(false);
    #define TASK "CPASS"
    if(fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
//        freopen(TASK".OUT", "w", stdout);
    }

    cin >> n >> m;
    cin >> s >> t;
    cin >> l >> r;

    REP(i, m)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    memset(du, 0x3f, sizeof du);
    memset(dv, 0x3f, sizeof dv);
    Precompute(l, du);
    Precompute(r, dv);

    ans = du[r];
    Calc(s, t);
    Calc(t, s);

    cout << ans << '\n';

    return 0;
}
/*
6 6
1 6
5 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1

*/

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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