oj.uz

Submission #855639

# Submission time Handle Problem Language Result Execution time Memory
855639 2023-10-01T15:13:57 Z Hakiers Robot (JOI21_ho_t4) C++17
0 / 100
 84 ms 19252 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();
    	
    	
    	
    		
    	long long res = min(cost[n][0], cost[n][1]);
    	if(res == oo) res = -1;
    		
    	cout << res << "\n";
    	
     
    }

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 1 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 84 ms 19252 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 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Incorrect 2 ms 8796 KB Output isn't correct
4 Halted 0 ms 0 KB -