Submission #1182865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182865		SmuggingSpun	Robot (JOI21_ho_t4)	C++20	24 / 100	364 ms	43728 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];
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);
	}
	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 + p[i])){
					pq.push(make_pair(d[v], v));
				}
				if(cnt[v][c[i]].size() == 2){
					int vv = cnt[v][c[i]][0] ^ cnt[v][c[i]][1] ^ i;
					if(minimize(d[vv = a[vv] ^ b[vv] ^ v], w + p[i])){
						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:21:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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