Submission #1182872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182872		SmuggingSpun	Robot (JOI21_ho_t4)	C++20	0 / 100	75 ms	27596 KiB

Main

#include<bits/stdc++.h>
#define taskname "D"
using namespace std;
typedef long long ll;
template<class T>bool minimize(T& a, T b){
	if(a > b){
		a = b;
		return true;
	}
	return false;
}
const int lim = 1e5 + 5;
const int LIM = 2e5 + 5;
int n, m, a[LIM], b[LIM], c[LIM], p[LIM];
vector<int>g[lim];
map<int, vector<int>>cnt[lim];
map<int, ll>cost[lim];
ll d[lim];
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> a[i] >> b[i] >> c[i] >> p[i];
		g[a[i]].emplace_back(i);
		g[b[i]].emplace_back(i);
		cnt[a[i]][c[i]].emplace_back(i);
		cnt[b[i]][c[i]].emplace_back(i);
		cost[a[i]][c[i]] += p[i];
		cost[b[i]][c[i]] += p[i];
	}
	for(int i = 1; i <= n; i++){
		for(auto& [foo, ve] : cnt[i]){
			sort(ve.begin(), ve.end(), [&] (int x, int y){
				return p[x] > p[y];	
			});
		}
	}
	memset(d, 0x0f, sizeof(d));
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>pq;
	pq.push(make_pair(d[1] = 0, 1));
	while(!pq.empty()){
		pair<ll, int>_current = pq.top();
		pq.pop();
		ll w = _current.first;
		int u = _current.second;
		if(w == d[u]){
			for(int& i : g[u]){
				int v = a[i] ^ b[i] ^ u;
				if(cnt[u][c[i]].size() == 1 && minimize(d[v], w)){
					pq.push(make_pair(w, v));
				}
				if(minimize(d[v], w + min(ll(p[i]), cost[u][c[i]] - p[i]))){
					pq.push(make_pair(d[v], v));
				}
				if(i == cnt[u][c[i]][0]){
					ll temp = w + cost[v][c[i]] - p[i];
					for(int& j : cnt[v][c[i]]){
						if(j != i){
							int vv = a[j] ^ b[j] ^ v;
							if(minimize(d[vv], temp - p[j])){
								pq.push(make_pair(d[vv], vv));
							}
						}
					}
				}
			}
		}
	}
	cout << (d[n] == d[0] ? -1LL : d[n]);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:22:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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