Submission #1283607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283607		nemkho	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	300 ms	40516 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define pr pair <ll, int>
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 5;
struct haha
{
    ll val;
    int ver, type, g;
};
struct cmp
{
    bool operator() (const haha &a, const haha &b)
    {
        return a.val > b.val;
    }
};
int n, m, s, t, U, V;
vector <pr> a[N], g_s[N], g_t[N];
ll dist[N][5], d_s[N], d_t[N];

void inp()
{
    cin >> n >> m >> s >> t >> U >> V;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        ll w;
        cin >> x >> y >> w;
        a[x].push_back({w, y});
        a[y].push_back({w, x});
    }
}

void dijkstra_ST()
{
    priority_queue<pr, vector<pr>, greater<pr>> q;
    q.push({0, s});
    for (int i = 1; i <= n; i++)
        d_s[i] = 1e18;
    d_s[s] = 0;
    while (!q.empty())
    {
        int u = q.top().se;
        ll k = q.top().fi;
        q.pop();
        if (k > d_s[u])
            continue;
        for (pr i : a[u])
        {
            int v = i.se;
            ll val = k + i.fi;
            if (d_s[v] > val)
            {
                d_s[v] = val;
                q.push({val, v});
            }
        }
    }
}

void dijkstra_TS()
{
    priority_queue<pr, vector<pr>, greater<pr>> q;
    q.push({0, t});
    for (int i = 1; i <= n; i++)
        d_t[i] = 1e18;
    d_t[t] = 0;
    while (!q.empty())
    {
        int u = q.top().se;
        ll k = q.top().fi;
        q.pop();
        if (k > d_t[u])
            continue;
        for (pr i : a[u])
        {
            int v = i.se;
            ll val = k + i.fi;
            if (d_t[v] > val)
            {
                d_t[v] = val;
                q.push({val, v});
            }
        }
    }
}

vector<pr> *getTmp(int g, int u)
{
    if (g == 1)
        return &g_t[u];
    if (g == 2)
        return &g_s[u];
    return &a[u];
}

void dijkstra_UV ()
{
    priority_queue <haha, vector<haha>, cmp> q;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= 3; j++)
            dist[i][j] = 1e18;
    dist[U][0] = 0;
    q.push({0, U, 0, 0});
    while (!q.empty())
    {
        int u = q.top().ver, type = q.top().type, g = q.top().g;
        ll k = q.top().val;
       // cout << u << " " << type << " " << g << " " << k << "\n";
        q.pop();
        if (k > dist[u][type])
            continue;
        vector <pr> *tmp = getTmp(g, u);
        for (pr i : *tmp)
        {
            ll val = k + i.fi;
            int v = i.se;

            if (type == 0)
            {
                int graph = 0;
                if (d_t[u] + d_s[v] + i.fi == d_s[t])
                    graph = 1;
                else if (d_s[u] + d_t[v] + i.fi == d_s[t])
                    graph = 2;
               // cout << u << " " << v << " " << graph << "\n";
                if (graph && dist[v][1] > k && d_s[t] != 1e18)
                {
                    q.push({k, v, 1, graph});
                    dist[v][1] = k;
                }
                if (dist[v][0] > val)
                {
                    q.push({val, v, 0, 0});
                    dist[v][0] = val;
                }
            }

            if(type == 1)
            {
                if (dist[v][1] > k)
                {
                    q.push({k, v, 1, g});
                    dist[v][1] = k;
                }
            }

            if (type == 2)
            {
                if (dist[v][2] > val)
                {
                    dist[v][2] = val;
                    q.push({val, v, 2, 0});
                }
            }
        }
        if (type == 1)
        {
            for (pr i : a[u])
            {
                int v = i.se;
                ll val = i.fi + k;
                if (dist[v][2] > val)
                {
                    q.push({val, v, 2, 0});
                    dist[v][2] = val;
            }
                }
        }
    }
}

void build()
{
    for (int u = 1; u <= n; u++)
    {
        for (pr i : a[u])
        {
            int v = i.se;
            ll w = i.fi;
            if (d_s[u] + w + d_t[v] == d_s[t])
            {
                g_s[u].push_back({w, v});
                g_t[v].push_back({w, u});
            }
        }
    }
}

void solve()
{
    dijkstra_ST();
    dijkstra_TS();
    build();
//    for (int i = 1; i <= n; i++)
//    {
//        cout << i << " ";
//        for (pr j : g_t[i])
//            cout << j.se << " ";
//        cout << "\n";
//    }
    dijkstra_UV();
    cout << (min({dist[V][1], dist[V][2], dist[V][0]}) > 1e18 ? - 1 : min({dist[V][1], dist[V][2], dist[V][0]}));
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    inp();
    solve();
}

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