Submission #444768

#	Time	Username	Problem	Language	Result	Execution time	Memory
444768		dutch	Robot (JOI21_ho_t4)	C++17	100 / 100	1334 ms	100144 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];
map<int, vector<array<int, 2>>> g[LIM];
map<int, int> s[LIM];
map<int, bool> vis[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]][a[2][i]].push_back({a[1][i], i});
		g[a[1][i]][a[2][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){
			int f = (u -= n) % m;
			u = a[u >= m][f];
			if(!vis[u][a[2][f]]){
				for(auto &[v, e] : g[u][a[2][f]])
					if(e != f)
						add(v, dist + s[u][a[2][e]] - a[3][e]);
				vis[u][a[2][f]] = 1;
			}
			if(u == n-1) ans = min(ans, dist + a[3][f]);
		}else{
			if(!vis[u][0]){
				for(auto &[z, h] : g[u]){
					for(auto &[v, e] : h){
						add(v, dist + min(s[u][a[2][e]] - a[3][e], a[3][e]));
						add(n+e+m*(u == a[0][e]), dist);
					}
				}
				vis[u][0] = 1;
			}
			if(u == n-1) ans = min(ans, dist);
		}
	}
	cout << (ans == INF ? -1 : ans);
}

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