Submission #855802

#	Time	Username	Problem	Language	Result	Execution time	Memory
855802		Hakiers	Robot (JOI21_ho_t4)	C++17	0 / 100	3033 ms	333220 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];
map<int, long long> cost[MAXN][2];

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

	cost[a][0][c] = oo;
	cost[a][1][c] = oo;
	cost[b][0][c] = oo;
	cost[b][1][c] = oo;
	
	mapa[a][c];
	mapa[b][c];
	
	mapa[a][c] += h;
	mapa[b][c] += h;

}

void dijkstra(){
	priority_queue<tuple<long long, int, int, int, pair<int, int>>> Q;
	Q.push({0, 1, 0, 0, {-1, 0}});
	
	cost[1][0][0] = oo;
	while(Q.size()){
		auto [d, v, krawedz, plac, in] = Q.top();
		Q.pop();
		
		if(cost[v][plac][krawedz] <= -d) continue;
		cost[v][plac][krawedz] = -d;
		
		
		for(auto [u, c, h] : G[v]){
			ll actcost;
			
			//placimy za krawedz
			actcost = h;
			if(cost[u][1][c] > cost[v][plac][krawedz] + actcost)
				Q.push({-(cost[v][plac][krawedz] + actcost), u, c, 1, {c, h}});
			
			//nie placimy za nia
			actcost = mapa[v][c] - h;
			if(c == in.first)
				actcost = max(actcost - (ll)in.second, (ll)0);
			if(cost[u][0][c] > cost[v][plac][krawedz] + actcost)
				Q.push({-(cost[v][plac][krawedz] + actcost), u, c, 0, {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);
	}
	

		
	dijkstra();
	ll res = oo;
	
	for(auto [u, c, h] : G[n])
		res = min(res, min(cost[n][0][c], cost[n][1][c]));
	
	if(res == oo)
	res = -1;
	
	cout << res << endl;
	

}

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