제출 #1288390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288390		jungle15	Robot (JOI21_ho_t4)	C++17	0 / 100	3094 ms	19092 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;

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

int n, m;
vector<to> adjc[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;
        adjc[u].push_back({v, c, p});
        adjc[v].push_back({u, c, p});
    }
}

vector<pair<int, long long>> adj[maxn + 2];

void precompute(void)
{
    unordered_map<int, long long> store;
    store.reserve(2 * n);
    for (int u = 1; u <= n; u++)
    {
        store.clear();
        for (const auto [v, c, p] : adjc[u])
            store[c] += p;
        for (const auto [v, c, p] : adjc[u])
            adj[u].push_back({v, min(1ll * p, store[c] - p)});
    }
}

const long long inf = 2e18;

long long dp[maxn + 2];

long long Dijkstra(const int source, const int sink)
{
    for (int i = 0; i < maxn + 2; 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, w] : adj[u])
            if (dp[v] > d + w)
                store.push({dp[v] = d + w, v});
    }
    return -1;
}

void solve(void)
{
    init();
    precompute();
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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