Submission #1125480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125480		Kel_Mahmut	Robot (JOI21_ho_t4)	C++20	100 / 100	1486 ms	101784 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, m;
	cin >> n >> m;
	vector<array<ll, 4>> edges(m);
	vector<map<int, vector<pair<int, int>>>> g(n);
	for(int i = 0; i < m; i++){
		for(int j = 0; j < 4; j++) cin >> edges[i][j];
		edges[i][0]--;
		edges[i][1]--;
	}	
	
	vector<unordered_map<ll, ll>> mpp(n);
	for(int i = 0; i < m; i++){
		auto [a, b, c, p] = edges[i];
		g[a][c].pb({b, p});
		g[b][c].pb({a, p});
		mpp[a][c] += p;
		mpp[b][c] += p;
	}

	ll ans = LLONG_MAX;
	vector<map<int, int>> vis(n); // colora gore
	priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> pq;
	pq.push({0, 0, 0, m + 1}); // d(ucuz), d, u, color (m + 1 bos demek)

	while(!pq.empty()){
		auto [ducuz, d, u, c] = pq.top(); pq.pop();
		if(vis[u][c]) continue;
		vis[u][c] = 1;

		if(u == n - 1){
			ans = min(ans, d);
		}

		if(c == m + 1){
			for(auto &[col, ar] : g[u]){
				for(auto [v, p] : ar){
					// color ile
					if(!vis[v][col]){
						ll cost = p;
						pq.push({d, d + cost, v, col});	
					}

					// bos
					if(!vis[v][m + 1]){
						ll cost = min(1ll * p, mpp[u][col] - p);
						pq.push({d + cost, d + cost, v, m + 1});
					}
				}
			}
		}
		else{
			for(auto [v, p] : g[u][c]){
				// color ile
				if(!vis[v][c]){
					pq.push({d, d + p, v, c});
				}
				// bos
				if(!vis[v][m + 1]){
					ll cost = mpp[u][c] - p;
					pq.push({ducuz + cost, ducuz + cost, v, m + 1});
				}
			}
		}
	}

	cout << (ans == LLONG_MAX ? -1 : ans) << endl;
}

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