Submission #1037078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037078		ttttttttttttth	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	156 ms	25932 KiB

commuter_pass

// Author: Ivan Teo
// Created: Sun Jul 28 10:10:07 2024

#define TASKNAME "joi"
#include <bits/stdc++.h>
using namespace std;

#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define int long long
using vi = vector<int>;
using ii = pair<int, int>;
#define pb emplace_back
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) v.begin() + 1, v.end()
#define alll(v) v.begin(), v.end()
#define db(x) cerr << "[" << #x << " = " << x << "]"
#define ell cerr << "\n=========================================\n"
#define el cerr << '\n'
#define Unique(v) v.erase(unique(alll(v)), v.end())
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r)
{
    assert(l <= r);
    return uniform_int_distribution<int> (l, r)(rng);
}
template<int D, typename T> struct Vec : public vector < Vec < D - 1, T >>
{
    template<typename... Args> Vec(int n = 0, Args... args) : vector < Vec < D - 1, T >> (n, Vec < D - 1, T > (args...)) {}
};
template<typename T> struct Vec<1, T> : public vector<T>
{
    Vec(int n = 0, const T &val = T()) : vector<T>(n, val) {}
};
template<class T>void minimize(T &a, T b)
{
    if(a > b)
    {
        a = b;
    }
}
const int INF = 1e18;
const int N = 1e5 + 5;
vector<pair<int, int>>e[N];
void dijkstra(int vertex, vector<int> &d)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
    pq.emplace(d[vertex] = 0, vertex);
    bitset<N>vis;
    while(!pq.empty())
    {
        auto [w, u] = pq.top();
        pq.pop();
        if(w == d[u])
        {
            for(auto& [v, edge_w] : e[u])
            {
                int W = w + edge_w;
                if(W < d[v])
                {
                    pq.emplace(d[v] = W, v);
                }
            }
        }
    }
}
void ivan()
{
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        e[a].emplace_back(b, c);
        e[b].emplace_back(a, c);
    }
    vector<int>d_s(n + 1, INF), d_u(n + 1, INF), d_v(n + 1, INF), dp_u(n + 1, INF), dp_v(n + 1, INF);
    dijkstra(s, d_s);
    dijkstra(u, d_u);
    dijkstra(v, d_v);
    int ans = d_u[v];
    function<void(int)>dfs;
    dfs = [&] (int vertex)
    {
        if(dp_u[vertex] != INF)
        {
            return;
        }
        dp_u[vertex] = d_u[vertex];
        dp_v[vertex] = d_v[vertex];
        for(auto& [next_vertex, w] : e[vertex])
        {
            if(d_s[next_vertex] + w == d_s[vertex])
            {
                dfs(next_vertex);
                minimize(dp_u[vertex], dp_u[next_vertex]);
                minimize(dp_v[vertex], dp_v[next_vertex]);
            }
        }
        minimize(ans, min(dp_v[vertex] + d_u[vertex], dp_u[vertex] + d_v[vertex]));
    };
    dfs(t);
    cout << ans;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    if (fopen(TASKNAME".inp", "r"))
    {
        freopen(TASKNAME".inp", "r", stdin);
        freopen(TASKNAME".out", "w", stdout);
    }
    int tc = 1;
    // cin >> tc;
    while (tc--) ivan();
    el, cerr << "Execution Time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s", el;
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(TASKNAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(TASKNAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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