Submission #444699

#	Time	Username	Problem	Language	Result	Execution time	Memory
444699		dutch	Robot (JOI21_ho_t4)	C++17	34 / 100	3082 ms	55412 KiB

Main

#include <bits/stdc++.h>
#define int int64_t
using namespace std;

const int LIM = 1e5, INF = 1e18;

int n, m, a[4][2*LIM], d[5*LIM];
vector<array<int, 2>> g[LIM];
unordered_map<int, int> s[LIM];
priority_queue<array<int, 2>> q;

void add(int i, int j){
	if(d[i] > j) q.push({-(d[i] = j), i});
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i=0; i<m; ++i){
		for(int j=0; j<4; ++j) cin >> a[j][i];
		--a[0][i], --a[1][i];
		g[a[0][i]].push_back({a[1][i], i});
		g[a[1][i]].push_back({a[0][i], i});
		s[a[0][i]][a[2][i]] += a[3][i];
		s[a[1][i]][a[2][i]] += a[3][i];
	}

	fill(d, d+n+m*2, INF);
	q.push({d[0] = 0, 0});

	int ans = INF;

	while(!q.empty()){
		int dist = -q.top()[0], u = q.top()[1]; q.pop();
		if(dist != d[u]) continue;

		if(u < n){
			for(auto &[v, e] : g[u])
				add(v, dist + s[u][a[2][e]] - a[3][e]);
		}else{
			int f = (u -= n) % m;
			u = a[u >= m][f];
			for(auto &[v, e] : g[u]){
				if(a[2][e] != a[2][f])
					add(v, dist + s[u][a[2][e]] - a[3][e]);
				else if(e != f)
					add(v, dist + s[u][a[2][e]] - a[3][e] - a[3][f]);
			}
		}
		if(u == n-1) ans = min(ans, dist);
		for(auto &[v, e] : g[u])
			add(n+e+m*(u == a[0][e]), dist + a[3][e]);
	}
	cout << (ans == INF ? -1 : ans);
}

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