Submission #532019

#	Time	Username	Problem	Language	Result	Execution time	Memory
532019		amunduzbaev	Robot (JOI21_ho_t4)	C++17	0 / 100	335 ms	33996 KiB

Main

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long
 
const int N = 1e5 + 5;
struct node{
	int a, b, c, p;
};
vector<node> edges[N];
vector<ar<int, 2>> ee[N];
int d[N];
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	for(int i=0;i<m;i++){
		node x; cin>>x.a>>x.b>>x.c>>x.p;
		edges[x.a].push_back(x);
		edges[x.b].push_back(x);
	}
	
	for(int i=1;i<=n;i++){
		map<int, int> mm;
		for(auto x : edges[i]){
			mm[x.c] += x.p;
		}
		
		for(auto x : edges[i]){
			int b = x.a + x.b - i;
			if(mm[x.c] > x.p){
				ee[b].push_back({i, min(x.p, mm[x.c] - x.p)});
			} else {
				ee[b].push_back({i, 0});
			}
		}
	}
	
	priority_queue<ar<int, 2>, vector<ar<int, 2>>, greater<ar<int, 2>>> q;
	q.push({0, n});
	memset(d, 127, sizeof d);
	d[n] = 0;
	while(!q.empty()){
		int u = q.top()[1], D = q.top()[0]; q.pop();
		if(D > d[u]) continue;
		for(auto x : ee[u]){
			if(d[x[0]] > d[u] + x[1]){
				d[x[0]] = d[u] + x[1];
				q.push({d[x[0]], x[0]});
			}
		}
	}
	
	if(d[1] > 1e18) cout<<-1<<"\n";
	else cout<<d[1]<<"\n";
}

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