Submission #855797

#	Time	Username	Problem	Language	Result	Execution time	Memory
855797		Hakiers	Robot (JOI21_ho_t4)	C++17	0 / 100	763 ms	58220 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 7;
const ll oo = 1e18;
vector<tuple<int, int, int>> G[MAXN];
map<int, long long> mapa[MAXN];
ll cost[MAXN][3];

void connect(int a, int b, int c, int h){
	G[a].push_back({b, c, h});
	G[b].push_back({a, c, h});
	
	mapa[a][c];
	mapa[b][c];
	
	mapa[a][c] += h;
	mapa[b][c] += h;

}

void dijkstra(){
	priority_queue<tuple<long long, int, int , pair<int, int>>> Q;
	Q.push({0, 1, 0, {0, 0}});
	
	// stan 0 przyszlismy taka gdzie zmieniamy wszystkie inne oprocz tej krawedzi
	// stan 1 przyszlismy taka gdzie zmieniamy krawedz placac za nia
	// stan 2 przyszlismy taka gdzie nie zmieniamy krawedzi przechodzimy za free
	while(Q.size()){
		auto [d, v, stan, in] = Q.top();
		Q.pop();
		
		if(cost[v][stan] <= -d) continue;
		cost[v][stan] = -d;
		
		
		
		
		for(auto [u, c, h] : G[v]){
			ll costact;
			if(stan == 0){
				// chemy do 0
				costact = mapa[v][c] - h;
				if(cost[u][0] > cost[v][stan] + costact)
					Q.push({-(cost[v][stan] + costact), u, 0, {0, 0}});
				//chcemy do 1
				costact = h;
				if(cost[u][1] > cost[v][stan] + costact)
					Q.push({-(cost[v][stan] + costact), u, 1, {c, h}});
				// chemy do 2
				costact = mapa[v][c] - h;
				if(costact == 0)
					if(cost[u][2] > cost[v][stan] + costact)
						Q.push({-(cost[v][stan] + costact), u, 2, {0, 0}});
			}
			else if(stan == 1){
				// chemy do 0
				costact = mapa[v][c] - h;
				if(c == in.first)
					costact = max(costact - (ll)in.second, (ll)0);
				if(cost[u][0] > cost[v][stan] + costact)
					Q.push({-(cost[v][stan] + costact), u, 0, {0, 0}});
				//chcemy do 1
				costact = h;
				if(cost[u][1] > cost[v][stan] + costact)
					Q.push({-(cost[v][stan] + costact), u, 1, {c, h}});
				// chemy do 2
				costact = mapa[v][c] - h;
				if(c == in.first)
					costact = max(costact - (ll)in.second, (ll)0);
				if(costact == 0)
					if(cost[u][2] > cost[v][stan] + costact)
						Q.push({-(cost[v][stan] + costact), u, 2, {0, 0}});
			}
			else{
				// chemy do 0
				costact = mapa[v][c] - h;
				if(cost[u][0] > cost[v][stan] + costact)
					Q.push({-(cost[v][stan] + costact), u, 0, {0, 0}});
				//chcemy do 1
				costact = h;
				if(cost[u][1] > cost[v][stan] + costact)
					Q.push({-(cost[v][stan] + costact), u, 1, {c, h}});
				// chemy do 2
				costact = mapa[v][c] - h;
				if(costact == 0)
					if(cost[u][2] > cost[v][stan] + costact)
						Q.push({-(cost[v][stan] + costact), u, 2, {0, 0}});
			}
		
		}
	
	}


}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	
	for(int i = 1; i <= m; i++){
		int a, b, c, h;
		cin >> a >> b >> c >> h;
		connect(a, b, c, h);
	}
	
	for(int i = 1; i <= n; i++)
		cost[i][0] = cost[i][1] = cost[i][2] = oo;
		
	dijkstra();
	ll res;
	res = min(cost[n][0], min(cost[n][1], cost[n][2]));
	
	if(res == oo)
	res = -1;
	
	cout << res << endl;
	

}

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