Submission #1288737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288737		jungle15	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	170 ms	22380 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define Jungle "JOI18_commuter_pass"
#define getbit(x, i) (((x) >> (i)) & 1)
#define cntbit(x) __builtin_popcount(x)
#define _(x) ((x) & -(x))
#define MASK(x) (1 << (x))
#define MULTEST \
    int nq;     \
    cin >> nq;  \
    while (nq--)

template <typename T>
void chkmin(T &a, T b)
{
    if (a > b)
        a = b;
}

template <typename T>
void chkmax(T &a, T b)
{
    if (a < b)
        a = b;
}

const int mod = 1e9 + 7;

int add(int x, int y)
{
    return (1ll * x + y) % mod;
}

int sub(int x, int y)
{
    return (1ll * x - y + mod) % mod;
}

int mul(int x, int y)
{
    return 1ll * x * y % mod;
}

void read(int &x)
{
    x = 0;
    int c = 0;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

const int maxn = 1e5;

int n, m, S, T, U, V;
vector<tuple<int, int, int>> edges;
vector<pair<int, int>> undirected_graph[maxn + 2];

void init(void)
{
    read(n);
    read(m);
    read(S);
    read(T);
    read(U);
    read(V);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        read(u);
        read(v);
        read(w);
        edges.push_back({u, v, w});
        undirected_graph[u].push_back({v, w});
        undirected_graph[v].push_back({u, w});
    }
}

const long long inf = 2e18;

void Dijkstra(const int source, long long dist[maxn + 2])
{
    for (int i = 1; i <= n; i++)
        dist[i] = inf;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> store;
    store.push({dist[source] = 0, source});
    while (store.size())
    {
        const auto [d, u] = store.top();
        store.pop();
        if (dist[u] != d)
            continue;
        for (const auto [v, w] : undirected_graph[u])
            if (dist[v] > d + w)
                store.push({dist[v] = d + w, v});
    }
}

queue<int> q;
int indeg[maxn + 2];
vector<int> DAG[maxn + 2], topo;
long long dist[3][maxn + 2], dpU[maxn + 2], dpV[maxn + 2], dp[maxn + 2];

void solve(void)
{
    init();
    Dijkstra(S, dist[0]);
    Dijkstra(U, dist[1]);
    Dijkstra(V, dist[2]);
    for (const auto &[u, v, w] : edges)
    {
        if (dist[0][u] + w == dist[0][v])
        {
            DAG[u].push_back(v);
            ++indeg[v];
        }
        if (dist[0][v] + w == dist[0][u])
        {
            DAG[v].push_back(u);
            ++indeg[u];
        }
    }
    q.push(S);
    while (q.size())
    {
        const int u = q.front();
        q.pop();
        topo.push_back(u);
        for (const int v : DAG[u])
            if (--indeg[v] == 0)
                q.push(v);
    }
    for (int i = 1; i <= n; i++)
        dpU[i] = dpV[i] = dp[i] = inf;
    dpU[S] = dist[1][S];
    dpV[S] = dist[2][S];
    dp[S] = dpU[S] + dpV[S];
    for (const int &u : topo)
    {
        chkmin(dp[u], min(dpU[u] + dist[2][u], dpV[u] + dist[1][u]));
        for (const int &v : DAG[u])
        {
            chkmin(dp[v], dp[u]);
            chkmin(dpU[v], min(dpU[u], dist[1][v]));
            chkmin(dpV[v], min(dpV[u], dist[2][v]));
        }
    }
    cout << min(dp[T], dist[1][V]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    if (fopen(Jungle ".inp", "r"))
    {
        freopen(Jungle ".inp", "r", stdin);
        freopen(Jungle ".out", "w", stdout);
    }

    // MULTEST
    solve();

    // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

    return 0;
}

Compilation message (stderr)

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

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