Submission #630540

#	Time	Username	Problem	Language	Result	Execution time	Memory
630540		QwertyPi	Robot (JOI21_ho_t4)	C++14	0 / 100	3072 ms	26056 KiB

Main

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define int long long
#pragma GCC optimize("Ofast")
using namespace std;

const int N = 100013, M = 400013;
int a[M], b[M], c[M], p[M];
vector<int> G[N];
vector<int> H[N];

int d2[N];
int d[M];
vector<int> gc[N], s[N];
int getM(int i, int colour){
	int l = lower_bound(gc[i].begin(), gc[i].end(), colour) - gc[i].begin() - 1;
	int r = upper_bound(gc[i].begin(), gc[i].end(), colour) - gc[i].begin() - 1;
	return s[i][r] - s[i][l];
}

struct Data{
	Data() = default;
	Data(int _q, int _e, int _r) : q(_q), eid(_e), r(_r){};
	int q, eid, r;
	bool operator< (const Data& o) const {
		return q < o.q;
	}
};

bool in_stack[M][2];

int32_t main(){
	int n, m;
	cin >> n >> m;
	a[0] = 0, b[0] = 1, c[0] = 0, p[0] = 0;
	for(int i = 1; i <= m; i++){
		cin >> a[i] >> b[i] >> c[i] >> p[i];
		G[a[i]].push_back(i);
		a[m + i] = b[i], b[m + i] = a[i], c[m + i] = c[i], p[m + i] = p[i];
		G[a[m + i]].push_back(m + i);
	}
	
	priority_queue<Data> pq;
	pq.push({0, 1, 0});
	for(int i = 1; i <= m * 2; i++){
		d[i] = (1LL << 60);
	}
	for(int i = 1; i <= n; i++){
		d2[i] = (1LL << 60);
	}
	for(int i = 1; i <= n; i++){
		vector<pair<int, int>> v;
		for(auto j : G[i]){
			v.push_back({c[j], p[j]});
		}
		sort(v.begin(), v.end());
		gc[i].push_back(0);
		s[i].push_back(0);
		for(auto j : v){
			gc[i].push_back(j.fi);
			s[i].push_back(s[i].back() + j.se);
		}
	}
	while(pq.size()){
		Data t = pq.top(); pq.pop();
		int dis = t.q, eid = t.eid, r = t.r;
		if((r ? d[b[eid]] : d2[eid]) < dis) continue;
		int v = r ? b[eid] : eid;
		for(auto i : G[v]){
			if(r){
				int cost_1 = dis + p[i];
				int cost_2 = dis + min(getM(v, c[i]) - p[i] - (c[i] == c[eid] ? p[eid] : 0), p[i]);
				if(cost_1 < d[i]){
					d[i] = cost_1;
					pq.push({d[i], i, 1});
				}
				if(cost_2 < d2[b[i]]){
					d2[b[i]] = cost_2;
					pq.push({d2[b[i]], b[i], 0});
				}
			}else{
				int cost_1 = dis + p[i];
				int cost_2 = dis + min(getM(v, c[i]) - p[i], p[i]);
				if(cost_1 < d[i]){
					d[i] = cost_1;
					pq.push({d[i], i, 1});
				}
				if(cost_2 < d2[b[i]]){
					d2[b[i]] = cost_2;
					pq.push({d2[b[i]], b[i], 0});
				}
			}
		}
	}
	int ans = d2[n];
	for(int i = 0; i <= m * 2; i++){
		if(b[i] == n){
			ans = min(ans, d[i]);
		}
	}
	cout << (ans >= (1LL << 60) ? -1 : ans) << endl;
}

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