Submission #1273909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273909		g4yuhg	Robot (JOI21_ho_t4)	C++20	34 / 100	3096 ms	51820 KiB

Main

#include<bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll, ll>
#define N 100005
using namespace std;

bool ghuy4g;

const ll inf = 1e18;

ll n, m;

struct piii {
	ll v, w, c;
};

vector<piii> adj[N];

ll dp[N];

map<int, ll> dp1[N], pf[N];

void dij() {
	priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> pq;
	for (int i = 1; i <= n; i ++) {
		dp[i] = inf;
	}
	dp[1] = 0;
	pq.push({dp[1], {1, 0}}); // ko co mau nao
	while (pq.size()) {
		auto c = pq.top().fi;
		auto u = pq.top().se;
		pq.pop();
		if (u.se == 0) {
			if (c > dp[u.fi]) {
				continue;
			}
			for (auto v : adj[u.fi]) {
				ll cost = v.w;
				cost = min(cost, pf[u.fi][v.c] - v.w);
				if (dp[v.v] > c + cost) {
					dp[v.v] = c + cost;
					pq.push({dp[v.v], {v.v, 0}});
				}
				// canh dac biet
				if (dp1[v.v].find(v.c) == dp1[v.v].end() || dp1[v.v][v.c] > c) {
					dp1[v.v][v.c] = c;
					pq.push({dp1[v.v][v.c], {v.v, v.c}});
				}
			}
		}
		else {
			if (c > dp1[u.fi][u.se]) continue;
			for (auto v : adj[u.fi]) {
				if (v.c != u.se) continue;
				ll cost = pf[u.fi][v.c] - v.w; // ko can canh nay
				if (dp[v.v] > c + cost) {
					dp[v.v] = c + cost;
					pq.push({dp[v.v], {v.v, 0}});
				}
			}
		}
	}
}

bool klinh;

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= m; i ++) {
		ll u, v, w, c;
		cin >> u >> v >> c >> w;
		pf[u][c] += w;
		pf[v][c] += w;
		adj[u].push_back({v, w, c});
		adj[v].push_back({u, w, c});
	}
	
	dij();
	if (dp[n] == inf) {
		cout << -1;
	}
	else {
		cout << dp[n];
	}
	
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024); 
	
	return 0;
}

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