제출 #518623

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
518623		KhoaHo	Robot (JOI21_ho_t4)	C++11	0 / 100	80 ms	21780 KiB

Main

/// KoJa
#include <bits/stdc++.h>
using namespace std;
#define task "QG04PAINT"
#define pb push_back
#define SZ(a) (a).begin(), (a).end()
#define SZZ(a, Begin, End) (a) + (Begin), (a) + (Begin) + (End)
#define BIT(a) (1LL << (a))
#define vec vector
#define fi first
#define se second

typedef long long ll;
typedef pair<ll, int> ii;

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }
void init()
{
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
}
void fastio()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int N = int(5e5) + 1000;
const ll INF = 1e18;
int n, m;
ll dist[N], best[N], sum[N];
struct Edge
{
    int v, c, cost;
    Edge() {}
    Edge(int _v, int _c, int _cost)
    {
        v = _v;
        c = _c;
        cost = _cost;
    }
};
vec<Edge> adj[N];
int main()
{
    fastio();
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, c, cost;
        cin >> u >> v >> c >> cost;
        adj[u].pb(Edge(v, c, cost));
        adj[v].pb(Edge(u, c, cost));
    }
    for (int i = 1; i <= n; i++)
        dist[i] = INF;
    for (int i = 1; i <= m; i++)
        best[i] = INF;
    dist[1] = 0;
    priority_queue<pair<ll, int>> q;
    q.push(make_pair(0LL, 1));
    while (!q.empty())
    {
        int u = q.top().se;
        ll cur = -q.top().fi;
        // cout << u << " " << -du << '\n';
        q.pop();
        if (cur != dist[u])
            continue;

        for (Edge x : adj[u])
        {
            sum[x.c] += x.cost;
            best[x.c] = min(best[x.c], dist[x.v]);
        }

        for (Edge x : adj[u])
        {
            int v = x.v;
            int c = x.c;
            int cost = x.cost;
            ll tmp = min(cost + 0LL, sum[c] - cost);

            if (minimize(dist[v], tmp + cur))
                q.push(make_pair(-dist[v], v));

            if (minimize(dist[v], best[c] + sum[c] - cost))
                q.push(make_pair(-dist[v], v));
        }

        for (Edge x : adj[u])
        {
            sum[x.c] = 0;
            best[x.c] = INF;
        }
    }
    if (dist[n] == INF)
        dist[n] = -1;
    cout << dist[n];
    return 0;
}

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

Main.cpp: In function 'void init()':
Main.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen(task ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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