제출 #532068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532068		amunduzbaev	Robot (JOI21_ho_t4)	C++17	34 / 100	785 ms	69732 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;
};
map<int, vector<ar<int, 2>>> edges[N], ee[N];
map<int, int> ss[N], uu[N];
int d[N], used[N];
node e[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 = e[i]; cin>>x.a>>x.b>>x.c>>x.p;
		edges[x.a][x.c].push_back({x.b, x.p});
		edges[x.b][x.c].push_back({x.a, x.p});
		ee[x.a][x.c].push_back({x.b, x.p});
		ee[x.b][x.c].push_back({x.a, x.p});
		ss[x.a][x.c] += x.p;
		ss[x.b][x.c] += x.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;
			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: 0 / 24
• Subtask 3: 0 / 42