oj.uz

Submission #855629

# Submission time Handle Problem Language Result Execution time Memory
855629 2023-10-01T14:34:48 Z Hakiers Robot (JOI21_ho_t4) C++17
0 / 100
 92 ms 20936 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
const long long oo = 1e18;
map<int, long long> mapa[MAXN];
vector<tuple<int, int, int>> G[MAXN];
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});
	
	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, {-1, 0}});
	// stan 1 zmieniam swoja krawedz a stan 0 zmienia szystkie inne
	
	while(Q.size()){
		auto [d, v, stan, in] = Q.top();
		Q.pop();
		
		if(cost[v][stan] <= -d) continue;
		cost[v][stan] = -d;
		
		Q.push({d, v, stan^1, in});
		
		
		for(auto [u, c, h] : G[v]){
			
			long long costmove;
			if(in.first == c && stan == 0)
				costmove = max((mapa[v][c] - (long long)in.second ) - (long long)h, (long long)0); 
			else if(stan == 0)
				costmove = (mapa[v][c] - (long long)h);
			else
				costmove = (mapa[v][c] - (long long)h);
				
			if(cost[u][stan] <= cost[v][stan] + costmove) continue;
			
			if(stan) Q.push({-(cost[v][stan] + costmove), u, stan, {c, h}});
			else Q.push({-(cost[v][stan] + costmove), u, stan, {-1, 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] = oo;
		
	dijkstra();
	
	
	if(cost[n][0] == oo)
		cost[n][0] = -1;
		
	if(cost[n][1] == oo)
		cost[n][1] == -1;
		
		
	cout << min(cost[n][0], cost[n][1]) << "\n";
	

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:78:14: warning: statement has no effect [-Wunused-value]
   78 |   cost[n][1] == -1;
      |   ~~~~~~~~~~~^~~~~

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8904 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Incorrect 2 ms 8796 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 20936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8904 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Incorrect 2 ms 8796 KB Output isn't correct
4 Halted 0 ms 0 KB -