Submission #652544

#	Time	Username	Problem	Language	Result	Execution time	Memory
652544		ymm	Robot (JOI21_ho_t4)	C++17	100 / 100	1205 ms	109576 KiB

Main

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const ll inf = 1e17;
const int N = 100'010;
map<int, ll> sum[N];
map<int, vector<pll>> colA[N];
map<int, ll> dis[N];
vector<tuple<int,int,ll,ll>> A[N];
int n, m;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (i,0,m) {
		int v, u, c, w;
		cin >> v >> u >> c >> w;
		--v; --u;
		A[v].push_back({u,c,w,0});
		A[u].push_back({v,c,w,0});
		sum[v][c] += w;
		sum[u][c] += w;
	}
	Loop (v,0,n) {
		for (auto &[u, c, w1, w2] : A[v]) {
			w2 = sum[v][c] - w1;
			colA[v][c].push_back({u,w2});
			dis[v][c] = inf;
		}
		dis[v][-1] = inf;
	}
	set<tuple<ll,int,int>> s = {{0, -1, 0}};
	dis[0][-1] = 0;
	while (s.size()) {
		auto [d, c, v] = *s.begin();
		s.erase(s.begin());
		if (c == -1) {
			for (auto [u, c, w1, w2] : A[v]) {
				ll w = min(w1, w2);
				if (d + w < dis[u][-1]) {
					s.erase({dis[u][-1], -1, u});
					dis[u][-1] = d+w;
					s.insert({dis[u][-1], -1, u});
				}
				if (d < dis[u][c]) {
					s.erase({dis[u][c], c, u});
					dis[u][c] = d;
					s.insert({dis[u][c], c, u});
				}
			}
		} else {
			for (auto [u, w] : colA[v][c]) {
				if (d + w < dis[u][-1]) {
					s.erase({dis[u][-1], -1, u});
					dis[u][-1] = d+w;
					s.insert({dis[u][-1], -1, u});
				}
			}
		}
	}
	cout << (dis[n-1][-1] == inf? -1: dis[n-1][-1]) << '\n';
}

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