Submission #1129943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129943		NoMercy	Robot (JOI21_ho_t4)	C++20	100 / 100	887 ms	82628 KiB

Main

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

typedef long long ll;

const ll inf = 1e16 + 66;

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N, M;
    cin >> N >> M;
    map<ll, vector<array<ll, 3>>> g[N];
    map<ll, ll> sum[N];
    for (int i = 0;i < M;i ++) {
        ll u, v, c, p;
        cin >> u >> v >> c >> p;
        -- u;
        -- v;
        g[u][c].push_back({v, c, p});
        g[v][c].push_back({u, c, p});
        sum[u][c] += p;
        sum[v][c] += p;
    }

    map<ll, ll> dp[N];
    vector<ll> dist(N, inf);
    dist[0] = 0;
	priority_queue<array<ll, 3>> pq;
	pq.push({0, 0, 0});
    while (pq.size() > 0) {
        auto [val, u, c] = pq.top();
        pq.pop();
        
        ll tmp;
        if (c == 0) {
            if (dist[u] != -val) continue;
            for (auto [fi, se] : g[u]) {
				for (auto [v, _c, p] : se) {
					tmp = sum[u][_c] - p - val;
					if (tmp < dist[v]) {
						dist[v] = tmp;
						pq.push({-dist[v], v, 0});
					}

					tmp = p - val;
					if (tmp < dist[v]) {
						dist[v] = tmp;
						pq.push({-dist[v], v, 0});
					}

					tmp = -val;
					if (dp[v].count(_c) == 0 || tmp < dp[v][_c]) {
						dp[v][_c] = tmp;
						pq.push({-dp[v][_c], v, _c});
					}
				}
			}
        } else {
            if (dp[u][c] != -val) continue;
            for (auto [v, _c, p] : g[u][c]) {
				tmp = sum[u][c] - p;
				if (tmp - val < dist[v]) {
					dist[v] = tmp - val;
					pq.push({-dist[v], v, 0});
				}
			}
        }
    }
    cout << (dist[N - 1] < inf ? dist[N - 1] : -1) << "\n";
}

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