Submission #1293981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293981		thaibeo123	Robot (JOI21_ho_t4)	C++20	100 / 100	331 ms	52524 KiB

Main

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

#define NAME "A"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define MASK(x) (1ll << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

const int N = 3e5 + 5;
const ll inf = 1e18;

int n, m, sz;
ll dist[N];
vector<pair<int, ll>> g[N];
vector<pair<int, pair<int, int>>> adj[N];

void dijkstra() {
    for (int i = 1; i <= sz; i++) {
        dist[i] = inf;
    }
    dist[1] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    pq.push({dist[1], 1});
    while (pq.size()) {
        ll cost = pq.top().fi;
        int u = pq.top().se;
        pq.pop();
        if (cost > dist[u]) continue;
        for (auto it : g[u]) {
            int v = it.fi;
            ll w = it.se;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

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

void solve() {
    sz = n;
    for (int t = 1; t <= n; t++) {
        sort(all(adj[t]));
        for (int i = 0; i < (int)adj[t].size(); i++) {
            //cout << t << " " << i << "\n";
            int j = i;
            while (j + 1 < (int)adj[t].size() && adj[t][i].fi == adj[t][j + 1].fi) {
                j++;
            }
            int len = j - i + 1;
            int u = t;
            if (len == 1) {
                g[u].pb({adj[t][i].se.fi, 0});
            }
            else {
                int cur = ++sz;
                g[u].pb({cur, 0});
                ll sumP = 0;
                for (int k = i; k <= j; k++) {
                    sumP += adj[t][k].se.se;
                }
                for (int k = i; k <= j; k++) {
                    int v = adj[t][k].se.fi;
                    int p = adj[t][k].se.se;
                    g[u].pb({v, p});
                    g[v].pb({cur, 0});
                    g[cur].pb({v, sumP - p});
                }
            }
            i = j;
        }
    }
    dijkstra();
    if (dist[n] == inf) dist[n] = -1;
    cout << dist[n];
}

signed main() {
    if (fopen(NAME".INP", "r")) {
        freopen(NAME".INP", "r", stdin);
        freopen(NAME".OUT", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int t = 1;
    //cin >> t;
    while (t--) {
        input();
        solve();
    }

    return 0;
}

Compilation message (stderr)

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

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