Submission #1182879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182879		SmuggingSpun	Robot (JOI21_ho_t4)	C++20	0 / 100	696 ms	69092 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];
	}
	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]){
			map<int, ll>prog;
			map<int, int>V;
			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(prog[c[i]] == 0){
					prog[c[i]] = w + cost[v][c[i]];
					V[c[i]] = v;
				}
				else if(minimize(prog[c[i]], w + cost[v][c[i]])){
					V[c[i]] = v;
				}
			}
			for(auto& [color, W] : prog){
				int v = V[color];
				for(int& j : cnt[v][color]){
					int vv = a[j] ^ b[j] ^ v;
					if(minimize(d[vv], W - 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