Submission #1083419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083419		icyalmond	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	343 ms	63428 KiB

commuter_pass

#include <bits/stdc++.h>
#define ii pair <int, int>
#define ll long long
#define llll pair <ll, ll>
#define ld long double
#define ull unsigned long long
#define el "\n"
#define sp " "
#define fi first
#define se second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define __lcm(a, b) (a / __gcd(a, b) * b)
#define sq(x) (x) * (x)
#define sqr(x) sqrtl(x)
#define cbr(x) cbrtl(x)
#define sz(a) (ll)(a.size())
using namespace std;

const ld PI = acos(-1); const int INFI = 1e9 + 7; const ll INFL = 2e18 + 7;

int n, m, s, t, u, v, x[200005], y[200005], z[200005];
vector <pair <pair <int, ll>, int>> g[100005];
ll d[5][100005];
priority_queue <pair <pair <ll, int>, int>, vector <pair <pair <ll, int>, int>>, greater <pair <pair <ll, int>, int>>> pq;

void Dijkstra_1(int start, int id)
{
    for (int i = 1; i <= n; i++) d[id][i] = INFL;
    d[id][start] = 0;
    pq.push({{0, start}, 1});
    while (sz(pq))
    {
        pair <pair <ll, int>, int> temp = pq.top();
        pq.pop();
        for (pair <pair <int, ll>, int> i : g[temp.fi.se])
        {
            if (temp.fi.fi + i.fi.se < d[id][i.fi.fi])
            {
                d[id][i.fi.fi] = temp.fi.fi + i.fi.se;
                pq.push({{temp.fi.fi + i.fi.se, i.fi.fi}, 1});
            }
        }
    }
}

void Dijkstra_2(int start)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= 4; j++) d[j][i] = INFL;
    }
    d[1][start] = 0;
    pq.push({{0, start}, 1});
    while (sz(pq))
    {
        pair <pair <ll, int>, int> temp = pq.top();
        pq.pop();
        //cout << temp.fi.fi << sp << temp.fi.se << sp << temp.se << el;
        for (pair <pair <int, ll>, int> i : g[temp.fi.se])
        {
            if ((temp.se == 1 && i.se == 4) || ((temp.se == 2 || temp.se == 3) && (i.se != 4 && i.se != temp.se)) || (temp.se == 4 && i.se != 4)) continue;
            if (temp.fi.fi + i.fi.se < d[i.se][i.fi.fi])
            {
                d[i.se][i.fi.fi] = temp.fi.fi + i.fi.se;
                pq.push({{temp.fi.fi + i.fi.se, i.fi.fi}, i.se});
            }
        }
    }
}

void Solve()
{
    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 1; i <= m; i++)
    {
        cin >> x[i] >> y[i] >> z[i];
        g[x[i]].pub({{y[i], z[i]}, 1});
        g[y[i]].pub({{x[i], z[i]}, 1});
    }
    Dijkstra_1(s, 1);
    Dijkstra_1(t, 2);
    for (int i = 1; i <= m; i++)
    {
        g[x[i]].pub({{y[i], z[i]}, 4});
        g[y[i]].pub({{x[i], z[i]}, 4});
        if (d[1][x[i]] + z[i] + d[2][y[i]] == d[1][t])
        {
            g[x[i]].pub({{y[i], 0}, 2});
            g[y[i]].pub({{x[i], 0}, 3});
        }
        else if (d[2][x[i]] + z[i] + d[1][y[i]] == d[1][t])
        {
            g[y[i]].pub({{x[i], 0}, 2});
            g[x[i]].pub({{y[i], 0}, 3});
        }
    }
    Dijkstra_2(u);
    cout << min({d[1][v], d[2][v], d[3][v], d[4][v]});
}

int main()
{
    ios_base::sync_with_stdio(0);  cin.tie(NULL);  cout.tie(0);
 
    Solve();
    return 0;
}

//coded by icyalmond

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