Submission #1182833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182833		SmuggingSpun	Robot (JOI21_ho_t4)	C++20	0 / 100	21 ms	5956 KiB

Main

#include<bits/stdc++.h>
#define taskname "D"
using namespace std;
typedef long long ll;
const ll INF = 1e18;
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];
namespace sub1{
	struct Data{
		int u, e;
		bool change;
		ll w;
		Data(int _u, int _e, bool _change, ll _w) : u(_u), e(_e), change(_change), w(_w) {}
		friend bool operator <(const Data a, const Data b){
			return a.w > b.w;
		}
	};
	void solve(){
		vector<vector<vector<ll>>>d(n + 1, vector<vector<ll>>(m + 1, vector<ll>(2, INF)));
		priority_queue<Data>pq;
		pq.push(Data(1, 0, false, d[1][0][0] = c[0] = 0));
		vector<int>cnt(m + 1, 0);
		while(!pq.empty()){
			Data current = pq.top();
			pq.pop();
			if(current.w == d[current.u][current.e][current.change]){
				for(int& i : g[current.u]){
					cnt[c[i]]++;
				}
				if(current.change){
					cnt[c[current.e]]--;
				}
				for(int& i : g[current.u]){
					int v = a[i] ^ b[i] ^ current.u;
					if(cnt[c[i]] == 1 && minimize(d[v][i][0], current.w)){
						pq.push(Data(v, i, false, current.w));
					}
					if(minimize(d[v][i][1], current.w + p[i])){
						pq.push(Data(v, i, true, d[v][i][1]));
					}
				}
				for(int& i : g[current.u]){
					cnt[c[i]] = 0;
				}
				cnt[c[current.e]] = 0;
			}
		}
		ll ans = INF;
		for(int i = 0; i <= m; i++){
			minimize(ans, min(d[n][i][0], d[n][i][1]));
		}
		cout << (ans == INF ? -1LL : ans);
	}
}
namespace sub23{
	void solve(){
		
	}
}
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);
	}
	if(n <= 1000 && m <= 2000){
		sub1::solve();
	}
	else{
		sub23::solve();
	}
}

Compilation message (stderr)

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

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