Submission #1022963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022963		sinatbtfard	Robot (JOI21_ho_t4)	C++17	100 / 100	1534 ms	144380 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second

using namespace std;

struct edge{
	int u, c; 
	ll p;
	edge(int _u, int _c, ll _p) : u(_u), c(_c), p(_p) {}
};
 
int n, m;
vector <map <int, vector <edge>>> adj; 
vector <map <int, ll>> dist, sum;
set <pair <ll, pair <int, int>>> s;

void dijkstra (){
    s.insert({0, {1, 0}});
	while (s.size()) {
		ll d = (*s.begin()).F;
		auto [v, c] = (*s.begin()).S;
		s.erase(s.begin());
		if (dist[v].count(c) && dist[v][c] <= d)
			continue;
		dist[v][c] = d;
		if (!c){
			for (auto Color : adj[v]) {
				for (auto [u, c, p] : Color.S) {
					s.insert({d + p, {u, 0}});
					s.insert({d + sum[v][c] - p, {u, 0}});
					s.insert({d, {u, c}});
				}
			}
		}
		else
			for (auto [u, c, p] : adj[v][c])
				s.insert({d + sum[v][c] - p, {u, 0}});
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin >> n >> m;
	adj.resize(n + 1);
	dist.resize(n + 1);
	sum.resize(n + 1);
	for (ll x, y, c, z, i = 1; i <= m; i ++) {
		cin >> x >> y >> c >> z;
		adj[x][c].push_back(edge(y, c, z));
		adj[y][c].push_back(edge(x, c, z));
		sum[x][c] += z, sum[y][c] += z;
	}
	dijkstra();
	cout << (!dist[n].count(0) ? -1 : dist[n][0]);
}

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