Submission #777083

#	Time	Username	Problem	Language	Result	Execution time	Memory
777083		teokakabadze	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	260 ms	31492 KiB

commuter_pass

#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
#define N 200005
#define pii pair<int, int>
#define piii pair<int, pii>
using namespace std;

int n, m, s, T, U, V, a, b, w, inf = 1e16, ans = 1e18, dp[N][2], d[N][3], f[N][3], F[N];
vector<pii> v[N];

void dijkstra(int st, int t)
{
    int u;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    for(int i = 1; i <= n; i++)
    d[i][t] = inf;
    d[st][t] = 0;
    q.push({0, st});
    while(q.size())
    {
        u = q.top().s;
        q.pop();
        if(f[u][t]) continue;
        f[u][t] = 1;
        for(auto x : v[u])
        if(d[x.f][t] > d[u][t] + x.s)
        {
            d[x.f][t] = d[u][t] + x.s;
            q.push({d[x.f][t], x.f});
        }
    }
}

void dfs(int u)
{
    if(F[u]) return;
    F[u] = 1;
    dp[u][0] = d[u][1];
    dp[u][1] = d[u][2];
    for(auto x : v[u])
    if(d[u][0] == d[x.f][0] + x.s) 
    {
        dfs(x.f);
        dp[u][0] = min(dp[u][0], dp[x.f][0]);
        dp[u][1] = min(dp[u][1], dp[x.f][1]);
    }
    ans = min(ans, min(dp[u][0] + d[u][2], dp[u][1] + d[u][1]));
}

main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m >> s >> T >> U >> V;
    while(m--)
    {
        cin >> a >> b >> w;
        v[a].pb({b, w});
        v[b].pb({a, w});
    }
    dijkstra(s, 0);
    dijkstra(U, 1);
    dijkstra(V, 2);
    dfs(T);
    cout << min(d[V][1], ans) << '\n';
}

Compilation message (stderr)

commuter_pass.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main()
      | ^~~~

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