Submission #518628

#	Time	Username	Problem	Language	Result	Execution time	Memory
518628		KhoaHo	Robot (JOI21_ho_t4)	C++11	100 / 100	158 ms	21276 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, 1) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b, 1) : 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(2e5) + 1000;
const ll INF = 1e18;
int n, m;
ll dist[N], best[N], sum[N];
struct Edge
{
    int to, c;
    ll cost;
    Edge(int _to = 0, int _c = 0, ll _cost = 0)
    {
        to = _to;
        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;
        ll 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;
        sum[i] = 0;
    }
    dist[1] = 0;
    priority_queue<ii> q;
    q.push(ii(0, 1));
    while (!q.empty())
    {
        int u = q.top().se;
        ll du = -q.top().fi;
        // cout << u << " " << -du << '\n';
        q.pop();
        if (du != dist[u])
            continue;

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

        for (Edge x : adj[u])
        {
            if (minimize(dist[x.to], du + min(x.cost, sum[x.c] - x.cost)))
                q.push(ii(-dist[x.to], x.to));
            if (minimize(dist[x.to], best[x.c] + sum[x.c] - x.cost))
                q.push(ii(-dist[x.to], x.to));
        }

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

Compilation message (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: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42