Submission #1186152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186152		jerzyk	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	266 ms	49700 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1'000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1'000'000'007LL;
const int N = 1<<19;
ll d1[N], d2[N];
pair<pair<int, int>, int> e[N];
vector<pair<int, int>> ed[N];
ll dis[N];
int vis[N];

void Dijkstra(int n, int s)
{
    int v;
    priority_queue<pair<ll, int>> q;
    for(int i = 1; i <= n; ++i)
        {dis[i] = I; vis[i] = 0;}
    dis[s] = 0;
    q.push(make_pair(0LL, s));
    while((int)q.size() > 0)
    {
        v = q.top().nd; q.pop();
        if(vis[v]) continue;
        vis[v] = 1;
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            ll o = dis[v] + (ll)ed[v][i].nd;
            if(o < dis[ed[v][i].st])
            {
                dis[ed[v][i].st] = o;
                q.push(make_pair(-o, ed[v][i].st));
            }
        }
    }
}

void Solve()
{
    int n, m, a, b, c;
    int s, t, u, v;
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    for(int i = 1; i <= m; ++i)
    {
        cin >> a >> b >> c;
        ed[a].pb(pair{b, c});
        ed[b].pb(pair{a, c});
        e[i] = pair{pair{a, b}, c};
    }
    Dijkstra(n, s);
    for(int i = 1; i <= n; ++i) d1[i] = dis[i];
    Dijkstra(n, t);
    for(int i = 1; i <= n; ++i) d2[i] = dis[i];
    
    for(int i = 1; i <= n; ++i)
    {
        ed[i].pb(pair{i + n, 0});
        ed[i].pb(pair{i + 2 * n, 0});

        ed[i + n].pb(pair{i + 3 * n, 0});
        ed[i + 2 * n].pb(pair{i + 3 * n, 0});
    }
    for(int i = 1; i <= m; ++i)
    {
        a = e[i].st.st; b = e[i].st.nd; c = e[i].nd;
        if(d1[a] > d1[b]) swap(a, b);
        // cout << "E: " << a << " " << b << " " << c << " | " << d1[a] << " " << d2[b] << "\n";
        ed[a + 3 * n].pb(pair{b + 3 * n, c});
        ed[b + 3 * n].pb(pair{a + 3 * n, c});
        if(d1[a] + c + d2[b] != d1[t]) continue;
        ed[a + n].pb(make_pair(b + n, 0));
        ed[b + 2 * n].pb(make_pair(a + 2 * n, 0));
    }
    Dijkstra(n * 4, u);
    cout << dis[v + 3 * n] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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