Submission #855639

#	Time	Username	Problem	Language	Result	Execution time	Memory
855639		Hakiers	Robot (JOI21_ho_t4)	C++17	0 / 100	84 ms	19252 KiB

Main

    #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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42