Submission #1288662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288662		jungle15	Robot (JOI21_ho_t4)	C++17	100 / 100	91 ms	15188 KiB

Main

#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 "JOI21_ho_t4"
#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;
}

const int maxn = 1e5, maxm = 2e5;

struct to
{
    int v, c, p;
};

int n, m;
vector<to> adj[maxn + 2];

void init(void)
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, c, p;
        cin >> u >> v >> c >> p;
        adj[u].push_back({v, c, p});
        adj[v].push_back({u, c, p});
    }
}

const long long inf = 2e18;

long long dp[maxn + 2], color[maxm + 2], sum[maxm + 2];

long long Dijkstra(const int source, const int sink)
{
    for (int i = 1; i <= n; i++)
        dp[i] = inf;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> store;
    store.push({dp[source] = 0, source});
    while (store.size())
    {
        const auto [d, u] = store.top();
        if (u == sink)
            return d;
        store.pop();
        if (dp[u] != d)
            continue;
        for (const auto [v, c, p] : adj[u])
        {
            sum[c] = 0;
            color[c] = inf;
        }
        for (const auto [v, c, p] : adj[u])
        {
            sum[c] += p;
            chkmin(color[c], dp[v]);
        }
        for (const auto [v, c, p] : adj[u])
        {
            long long val = min({d + p, d + sum[c] - p, color[c] + sum[c] - p});
            if (dp[v] > val)
                store.push({dp[v] = val, v});
        }
    }
    return -1;
}

void solve(void)
{
    init();
    cout << Dijkstra(1, n);
}

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)

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

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42