Submission #371330

#	Time	Username	Problem	Language	Result	Execution time	Memory
371330		cheissmart	Robot (JOI21_ho_t4)	C++14	100 / 100	984 ms	76380 KiB

Main

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
// #define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

void DBG() {
	cerr << "]" << endl;
}
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}

#define debug(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)

const int INF = 1e9 + 7, N = 1e5 + 7;

V<array<int, 3>> G[N]; // (to, color, cost)
unordered_map<int, V<array<int, 3>>> g[N]; // (to, color, cost)
unordered_map<int, ll> csum[N];
ll d[N];
unordered_map<int, ll> d2[N];

signed main()
{
	IO_OP;

	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v, c, p;
		cin >> u >> v >> c >> p;
		G[u].PB({v, c, p});
		G[v].PB({u, c, p});
		g[u][c].PB({v, c, p});
		g[v][c].PB({u, c, p});
		csum[u][c] += p;
		csum[v][c] += p;
	}
	memset(d, 0x3f, sizeof d);
	d[1] = 0;
	priority_queue<pair<ll, pi>, V<pair<ll, pi>>, greater<pair<ll, pi>>> pq;
	pq.push(MP(d[1], MP(1, 0)));
	while(pq.size()) {
		auto p = pq.top(); pq.pop();
		int u = p.S.F, c = p.S.S;
		if(c) {
			if(p.F > d2[u][c]) continue;
			for(auto e:g[u][c]) {
				int v = e[0], ec = e[1], cost = e[2];
				if(d2[u][c] + csum[u][ec] - cost < d[v]) {
					d[v] = d2[u][c] + csum[u][ec] - cost;
					pq.push(MP(d[v], MP(v, 0)));
				}
			}
		} else {
			if(p.F > d[u]) continue;
			for(auto e:G[u]) {
				int v = e[0], ec = e[1], cost = e[2];
				if(d[u] + csum[u][ec] - cost < d[v]) {
					d[v] = d[u] + csum[u][ec] - cost;
					pq.push(MP(d[v], MP(v, 0)));
				}
				if(d2[v].count(ec) == 0 || d[u] < d2[v][ec]) {
					d2[v][ec] = d[u];
					pq.push(MP(d2[v][ec], MP(v, ec)));
				}
				if(d[u] + cost < d[v]) {
					d[v] = d[u] + cost;
					pq.push(MP(d[v], MP(v, 0)));
				}
			}
		}
	}

	ll ans = d[n];
	if(ans > 1e17) ans = -1;
	cout << ans << '\n';

}

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