Submission #372512

#	Time	Username	Problem	Language	Result	Execution time	Memory
372512		Kevin_Zhang_TW	Robot (JOI21_ho_t4)	C++17	100 / 100	1040 ms	80848 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010, K = 4;
const ll inf = 1ll << 59;

unordered_map<int, vector<pair<int,int>>> edge[MAX_N];
int n, m;

ll dp[MAX_N], sec[MAX_N], fr[MAX_N], sef[MAX_N];

unordered_map<int, ll> mcdp[MAX_N];

struct info {
	ll cur, len, col, lst, mc;
	bool operator < (info b) const {
		return len > b.len;
	}
};

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int a, b, c, p, i = 0;i < m;++i) {
		cin >> a >> b >> c >> p;
		edge[a][c].pb(b, p);
		edge[b][c].pb(a, p);
	}
	for (int i = 1;i <= n;++i) {
		dp[i] = sec[i] = inf;
		fr[i] = sef[i] = -1;
	}

	priority_queue<info> pq;

	pq.push({1, 0, -1, -1, -1});

	dp[1] = sec[1] = 0;

	auto update = [&](int x, ll len, ll col, ll mc) {
		if (mc == -1) {
			bool ok = false;
			if (len < dp[x]) {
				swap(len, dp[x]);
				swap(col, fr[x]);
				ok = true;
			}
			if (len < sec[x] && fr[x] != col) {
				swap(len, sec[x]);
				swap(col, sef[x]);
				ok = true;
			}
			return ok;
		}
		else {
			if (!edge[x].count(mc)) return false;
			if (mcdp[x].count(mc)) 
				return chmin(mcdp[x][mc], len);
			else return mcdp[x][mc] = len, true;
		}
	};

	while (pq.size()) {
		auto [x, len, col, lst, mc] = pq.top(); pq.pop();


		DE(x, len, col);

		if (mc == -1) {
			if (len > sec[x]) continue;
		   	for (auto [c, vec] : edge[x]) {
				ll sum = 0;

				for (auto [u, cost] : vec) {
					if (u == lst && c != col) continue;
					sum += cost;
				}

				for (auto [u, cost] : vec) {
					if (u == lst) continue;

					ll need = sum - cost;

					if (c == col) need = inf;

					if (update(u, need + len, c, -1))
						pq.push({u, need + len, c, x, -1});

					if (update(u, cost + len, -1, -1))
						pq.push({u, cost + len, -1, x, -1});

					if (update(u, len, -1, c))
						pq.push({u, len, -1, x, c});
				}
			}
		}
		else {
			if (len > mcdp[x][mc]) continue;

			auto vec = edge[x][mc];

			int c = mc;

			ll sum = 0;

			for (auto [u, cost] : vec) 
				sum += cost;

			for (auto [u, cost] : vec) {
				if (u == lst) continue;

				ll need = sum - cost;

				if (update(u, need + len, c, -1))
					pq.push({u, need + len, c, x, -1});
			}
		}
	}

	if (dp[n] == inf) dp[n] = -1;

	cout << dp[n] << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
Main.cpp:81:3: note: in expansion of macro 'DE'
   81 |   DE(x, len, col);
      |   ^~

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