제출 #1265463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265463		kustov_vadim_533	Robot (JOI21_ho_t4)	C++20	34 / 100	3095 ms	53056 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define len(v) (int)((v).size())

const ll inf = 1e18;

struct edge{
	int to, cl, w;
	edge(int to, int cl, int w) : to(to), cl(cl), w(w) {};
};

bool operator<(edge a, edge b){
	if (a.w != b.w) return a.w < b.w;
	if (a.to != b.to) return a.to < b.to;
	return a.cl < b.cl;
}

inline void solve(){
	int n, m;
	cin >> n >> m;

	vector<vector<edge>> g(n);
	vector<unordered_map<int, ll>> cnt2(n);

	for (int i = 0; i < m; ++i){
		int a, b, c, p;
		cin >> a >> b >> c >> p;
		--a, --b, --c;

		cnt2[a][c] += p;
		cnt2[b][c] += p;

		g[a].emplace_back(b, c, p);
		g[b].emplace_back(a, c, p);
	}

	vector<map<edge, ll>> d(n);
	for (int i = 0; i < n; ++i){
		for (edge u : g[i]){
			d[i][u] = inf;
			d[i][edge(u.to, u.cl, 0)] = inf;
		}
	}

	set<pair<ll, pair<edge, int>>> q;
	d[0][edge(-1, m, 0)] = 0;
	q.insert({0, {edge(-1, m, 0), 0}});

	while (!q.empty()){
		edge rev = q.begin()->second.first;
		int v = q.begin()->second.second;

		q.erase(q.begin());

		for (edge u : g[v]){
			if (u.to == rev.to) continue;

			ll w = cnt2[v][u.cl] - u.w + d[v][rev];
			if (u.cl == rev.cl) w -= rev.w;
			if ((u.cl != rev.cl || rev.w > 0) && d[u.to][edge(v, u.cl, 0)] > w){
				pair<ll, pair<edge, int>> obj = {d[u.to][edge(v, u.cl, 0)], {edge(v, u.cl, 0), u.to}};
				if (q.find(obj) != q.end()){
					q.erase(obj);
				}
				d[u.to][edge(v, u.cl, 0)] = w;
				q.insert(obj);
			}


			w = d[v][rev] + u.w;
			if (d[u.to][edge(v, u.cl, u.w)] > w){
				pair<ll, pair<edge, int>> obj = {d[u.to][edge(v, u.cl, u.w)], {edge(v, u.cl, u.w), u.to}};
				if (q.find(obj) != q.end()){
					q.erase(obj);
				}
				d[u.to][edge(v, u.cl, u.w)] = w;
				q.insert(obj);
			}
		}
	}


	ll ans = inf;
	for (pair<edge, ll> p : d[n - 1]){
		ans = min(ans, p.second);
	}

	if (ans >= inf){
		cout << "-1\n";
	}
	else{
		cout << ans << '\n';
	}

}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(60);

	int t = 1;
//	cin >> t;

	while (t--) {
		solve();
	}
}

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