Submission #630491

#	Time	Username	Problem	Language	Result	Execution time	Memory
630491		QwertyPi	Robot (JOI21_ho_t4)	C++14	34 / 100	3076 ms	40832 KiB

Main

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define int long long
using namespace std;

const int N = 100013, M = 400013;
int a[M], b[M], c[M], p[M];
vector<int> G[N];
int d[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<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;
	pq.push({0, {0, 0}});
	for(int i = 1; i <= m * 2; i++){
		d[i][0] = d[i][1] = (1LL << 60);
	}
	while(pq.size()){
		pair<int, pii> t = pq.top(); pq.pop();
		int dis = t.fi, eid = t.se.fi, r = t.se.se;
		if(d[eid][r] < dis) continue;
		int u = a[eid], v = b[eid];
		unordered_map<int, int> M;
		for(auto i : G[v]){
			M[c[i]] += p[i];
		}
		for(auto i : G[v]){
			if(r){
				if(dis + p[i] < d[i][1]){
					d[i][1] = dis + p[i];
					// cout << "aM " << dis << ' ' << eid << ' ' << r << ' ' << i << ' ' << 1 << ' ' << d[i][1] << endl;
					pq.push({d[i][1], {i, 1}});
				}
				if(dis + min(M[c[i]] - p[i] - (c[i] == c[eid] && (eid - i) % m != 0 ? p[eid] : 0), p[i]) < d[i][0]){
					d[i][0] = dis + min(M[c[i]] - p[i] - (c[i] == c[eid] && (eid - i) % m != 0 ? p[eid] : 0), p[i]);
					// cout << "bM " << dis << ' ' << eid << ' ' << r << ' ' << i << ' ' << 0 << ' ' << d[i][0] << endl;
					pq.push({d[i][0], {i, 0}});
				}
			}else{
				if(dis + p[i] < d[i][1]){
					d[i][1] = dis + p[i];
					// cout << "cM " << dis << ' ' << eid << ' ' << r << ' ' << i << ' ' << 1 << ' ' << d[i][1] << endl;
					pq.push({d[i][1], {i, 1}});
				}
				if(dis + min(M[c[i]] - p[i], p[i]) < d[i][0]){
					d[i][0] = dis + min(M[c[i]] - p[i], p[i]);
					// cout << "dM " << dis << ' ' << eid << ' ' << r << ' ' << i << ' ' << 0 << ' ' << d[i][0] << endl;
					pq.push({d[i][0], {i, 0}});
				}
			}
		}
	}
	int ans = INT64_MAX;
	for(int i = 0; i <= m * 2; i++){
		if(b[i] == n){
			ans = min(ans, d[i][0]);
			ans = min(ans, d[i][1]);
		}
	}
	cout << (ans >= (1LL << 60) ? -1 : ans) << endl;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:33:7: warning: unused variable 'u' [-Wunused-variable]
   33 |   int u = a[eid], v = b[eid];
      |       ^

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