oj.uz

Submission #855797

# Submission time Handle Problem Language Result Execution time Memory
855797 2023-10-01T20:04:11 Z Hakiers Robot (JOI21_ho_t4) C++17
0 / 100
 763 ms 58220 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7632 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 3 ms 8028 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Incorrect 5 ms 8152 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 30516 KB Output is correct
2 Correct 68 ms 16984 KB Output is correct
3 Correct 186 ms 31936 KB Output is correct
4 Correct 96 ms 23628 KB Output is correct
5 Incorrect 763 ms 58220 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7632 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 3 ms 8028 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Incorrect 5 ms 8152 KB Output isn't correct
10 Halted 0 ms 0 KB -