Submission #761793

#	Time	Username	Problem	Language	Result	Execution time	Memory
761793		sysia	Robot (JOI21_ho_t4)	C++17	100 / 100	896 ms	85644 KiB

Main

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;
typedef tuple<int, int, int> F;

void solve(){
	int n, m; cin >> n >> m;
	vector<map<int, vector<T>>>g(n+1);
	vector<map<int, int>>dp(n+1), sum(n+1);
	for (int i = 0; i<m; i++){
		int a, b, c, p; cin >> a >> b >> c >> p;
		g[a][c].emplace_back(b, p);
		g[b][c].emplace_back(a, p);
		dp[a][c] = oo;
		dp[b][c] = oo;
		sum[a][c] += p;
		sum[b][c] += p;
	}
	// if (m == 1){
	// 	for (auto [x, c, p]: g[1]){
	// 		if (x == n){
	// 			cout << "0\n";
	// 			return;
	// 		}
	// 	}
	// 	cout << "-1\n";
	// 	return;
	// }
	priority_queue<F, vector<F>, greater<F>>pq;
	pq.push({0, 1, -1});
	//dp[v][c] = min koszt dotarcia do v z uzyciem ostatniej krawedzi c, z wymuszeniem jej zmiany pozniej na sciezce
	//dist[v] = min koszt po prostu dotarcia do v
	//stanow jest O(sum of deg v + n) = O(m + n) ?????
	vector<int>dist(n+1, oo);
	dist[1] = 0;
	while ((int)pq.size()){
		auto [d, v, c] = pq.top(); pq.pop();
		if (c == -1){
			if (dist[v] < d) continue;
			//nie wymuszamy zmiany koloru poprzedniej krawedzi
			for (auto [e, vt]: g[v]){
				for (auto [x, p]: vt){
					//a) nie zmieniamy koloru krawedzi v---x (czyli nie wymuszamy tez zadnej zmiany)
					int cost1 = sum[v][e] - p;
					if (dist[x] > d + cost1){
						dist[x] = d+cost1;
						pq.push({dist[x], x, -1});
					}
					//b) zmieniamy kolor krawedzi c, ale dalej nie wymuszamy zmiany
					//dirichlet ---> zawsze istnieje kolor na jaki mozemy zmienic
					int cost2 = p;
					if (dist[x] > d + cost2){
						dist[x] = d+cost2;
						pq.push({dist[x], x, -1});
					}
					//c) zmieniamy kolor krawedzi c, z wymuszeniem zmiany na pozniej dla nastepnej krawedzi na sciezce
					int cost3 = 0;
					if (dp[x][e] > d){
						dp[x][e] = d;
						pq.push({d, x, e});
					}
				}
			}
		} else {
			if (dp[v][c] < d) continue;
			//wymuszamy zmiane poprzedniej krawedzi c
			for (auto [x, p]: g[v][c]){
				int cost = sum[v][c] - p;
				if (dist[x] > d + cost){
					dist[x] = d+cost; 
					//nie oplaca sie zamieniac dwoch sasiednich krawedzi na optymalnej sciezce z koloru c na jakis inny kolor
					//gdyby tak bylo, to moglibysmy usunac jedna zmiane i miec lepszy wynik
					//wiec teraz nie wymuszamy zmiany koloru c
					pq.push({dist[x], x, -1});
				}
			}
			
		}
	}
	if (dist[n] == oo) cout << "-1\n";
	else cout << dist[n] << "\n";
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solve();

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:84:10: warning: unused variable 'cost3' [-Wunused-variable]
   84 |      int cost3 = 0;
      |          ^~~~~

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