Submission #319617

#	Time	Username	Problem	Language	Result	Execution time	Memory
319617		johutha	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	1460 ms	32500 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>

#define int int64_t

using namespace std;

struct graph
{
    int n;
    vector<vector<pair<int,int>>> adjlist;

    vector<int> svs;
    vector<int> mto;

    vector<int> dist;

    void dijkstra(int st)
    {
        priority_queue<pair<int,pair<int,int>>> pq;
        pq.emplace(0, make_pair(st, st));

        mto = svs;
        dist.assign(n, 1e17);

        while (!pq.empty())
        {
            auto [tm, nf] = pq.top();
            auto [curr, par] = nf;
            pq.pop();
            tm = -tm;
        
            if (dist[curr] >= tm) mto[curr] = min(mto[curr], mto[par]);
            if (dist[curr] <= tm) continue;
            dist[curr] = tm;

            // cerr << curr << " " << tm << "\n";

            for (auto np : adjlist[curr])
            {
                pq.emplace(-(np.second + tm), make_pair(np.first, curr));
            }
        }
    }  
};

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    int s, t, u, v;
    cin >> s >> t >> u >> v;
    s--; t--; u--; v--;

    graph g;
    g.n = n;

    g.adjlist.resize(n);
    g.dist.resize(n, 1e17);
    g.svs.resize(n, 1e17);
    g.mto.resize(n);

    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        g.adjlist[a].emplace_back(b, c);
        g.adjlist[b].emplace_back(a, c);
    }

    g.dijkstra(s);

    vector<int> frs = g.dist;
    int dst = g.dist[t];

    g.dijkstra(t);
    vector<int> frt = g.dist;

    g.dijkstra(u);

    int mmin = g.dist[v];

    auto calc = [&](int a, int b)
    {
        // cerr << a << "\n";
        g.dijkstra(a);
        g.svs = g.dist;

        for (int i = 0; i < n; i++)
        {
            // cerr << g.svs[i] << " ";
        }
        // cerr << "\n";

        for (int i = 0; i < n; i++)
        {
            // cerr << g.dist[i] << " ";
        }
        // cerr << "\n";

        g.dijkstra(t);
        auto crs = g.mto;

        g.dijkstra(b);

        for (int i = 0; i < n; i++)
        {
            if (frs[i] + frt[i] == dst)
            {
                mmin = min(mmin, g.dist[i] + crs[i]);
            }
        }
    };

    calc(u, v);
    calc(v, u);

    cout << mmin << "\n";
}

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