oj.uz

Submission #761793

# Submission time Handle Problem Language Result Execution time Memory
761793 2023-06-20T09:41:08 Z sysia Robot (JOI21_ho_t4) C++17
100 / 100
 896 ms 85644 KB 
//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

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

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 4 ms 1108 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 2 ms 724 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 1 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 23436 KB Output is correct
2 Correct 44 ms 12676 KB Output is correct
3 Correct 114 ms 19164 KB Output is correct
4 Correct 81 ms 16660 KB Output is correct
5 Correct 885 ms 80480 KB Output is correct
6 Correct 677 ms 74044 KB Output is correct
7 Correct 316 ms 64356 KB Output is correct
8 Correct 355 ms 50972 KB Output is correct
9 Correct 366 ms 51128 KB Output is correct
10 Correct 265 ms 44072 KB Output is correct
11 Correct 114 ms 35076 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 4 ms 1108 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 2 ms 724 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 127 ms 23436 KB Output is correct
22 Correct 44 ms 12676 KB Output is correct
23 Correct 114 ms 19164 KB Output is correct
24 Correct 81 ms 16660 KB Output is correct
25 Correct 885 ms 80480 KB Output is correct
26 Correct 677 ms 74044 KB Output is correct
27 Correct 316 ms 64356 KB Output is correct
28 Correct 355 ms 50972 KB Output is correct
29 Correct 366 ms 51128 KB Output is correct
30 Correct 265 ms 44072 KB Output is correct
31 Correct 114 ms 35076 KB Output is correct
32 Correct 80 ms 15404 KB Output is correct
33 Correct 88 ms 20416 KB Output is correct
34 Correct 313 ms 43684 KB Output is correct
35 Correct 247 ms 35252 KB Output is correct
36 Correct 270 ms 49116 KB Output is correct
37 Correct 302 ms 55316 KB Output is correct
38 Correct 304 ms 62488 KB Output is correct
39 Correct 87 ms 20260 KB Output is correct
40 Correct 361 ms 52172 KB Output is correct
41 Correct 366 ms 52556 KB Output is correct
42 Correct 438 ms 63576 KB Output is correct
43 Correct 156 ms 29176 KB Output is correct
44 Correct 264 ms 31840 KB Output is correct
45 Correct 273 ms 47660 KB Output is correct
46 Correct 229 ms 47940 KB Output is correct
47 Correct 275 ms 54512 KB Output is correct
48 Correct 896 ms 85644 KB Output is correct