Submission #371324

#	Time	Username	Problem	Language	Result	Execution time	Memory
371324		cheissmart	Robot (JOI21_ho_t4)	C++14	34 / 100	3052 ms	48328 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, ll> csum[N];
unordered_map<int, ll> dist[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});
		csum[u][c] += p;
		csum[v][c] += p;
	}
	dist[1][0] = 0;
	priority_queue<pair<ll, pi>, V<pair<ll, pi>>, greater<pair<ll, pi>>> pq;
	pq.push(MP(dist[1][0], MP(1, 0)));
	while(pq.size()) {
		auto p = pq.top(); pq.pop();
		int u = p.S.F, c = p.S.S;
		// debug(u, c, dist[u][c]);
		if(p.F > dist[u][c]) continue;
		for(auto e:G[u]) {
			int v = e[0], ec = e[1], cost = e[2];
			if(c < 0) {
				if(ec == -c) {
					if(dist[v].count(ec) == 0 || dist[u][c] + csum[u][ec] - cost < dist[v][ec]) {
						dist[v][ec] = dist[u][c] + csum[u][ec] - cost;
						pq.push(MP(dist[v][ec], MP(v, ec)));
					}
				}
				continue;
			}
			if(c != ec) {
				if(dist[v].count(ec) == 0 || dist[u][c] + csum[u][ec] - cost < dist[v][ec]) {
					dist[v][ec] = dist[u][c] + csum[u][ec] - cost;
					pq.push(MP(dist[v][ec], MP(v, ec)));
				}
			}
			if(dist[v].count(0) == 0 || dist[u][c] + cost < dist[v][0]) {
				dist[v][0] = dist[u][c] + cost;
				pq.push(MP(dist[v][0], MP(v, 0)));
			}
			if(dist[v].count(-ec) == 0 || dist[u][c] < dist[v][-ec]) {
				dist[v][-ec] = dist[u][c];
				pq.push(MP(dist[v][-ec], MP(v, -ec)));
			}
		}
	}
	ll ans = 1e18;
	for(auto p:dist[n])
		if(p.F >= 0) {
			ans = min(ans, p.S);
		}
	if(ans >= 1e18) ans = -1;
	cout << ans << '\n';


}

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