Submission #532069

#	Time	Username	Problem	Language	Result	Execution time	Memory
532069		amunduzbaev	Robot (JOI21_ho_t4)	C++17	100 / 100	1098 ms	104748 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

const int N = 1e5 + 5;
map<int, vector<ar<int, 2>>> edges[N];
map<int, int> ss[N], uu[N];
int d[N], used[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	for(int i=0;i<m;i++){
		int a, b, c, p; cin>>a>>b>>c>>p;
		edges[a][c].push_back({b, p});
		edges[b][c].push_back({a, p});
		ss[a][c] += p;
		ss[b][c] += p;
	}
	
	priority_queue<ar<int, 3>, vector<ar<int, 3>>, greater<ar<int, 3>>> q;
	q.push({0, 1, 0});
	memset(d, 127, sizeof d);
	while(!q.empty()){
		int D = q.top()[0], u = q.top()[1], c = q.top()[2]; q.pop();
		if(c < 0){ 
			c = abs(c);
			if(uu[u].count(c)) continue;
			uu[u][c];
			int& sum = ss[u][c];
			for(auto x : edges[u][c]){
				q.push({D + sum - x[1], x[0], 0});
			}
		} else if(!used[u]) {
			used[u] = 1;
			d[u] = D;
			for(auto [c, v] : edges[u]){
				int& sum = ss[u][c];
				for(auto x : v){
					q.push({D, x[0], -c});
					q.push({D + min(sum - x[1], x[1]), x[0], 0});
				}
			}
		}
	}
	
	if(d[n] > 1e18) cout<<-1<<"\n";
	else cout<<d[n]<<"\n";
}

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