oj.uz

Submission #857728

# Submission time Handle Problem Language Result Execution time Memory
857728 2023-10-06T17:23:43 Z dio_2 Robot (JOI21_ho_t4) C++17
0 / 100
 231 ms 37212 KB 
#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using ar = array<int, 3>;

const ll inf = (ll)1e18;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m;
	cin >> n >> m;
	
	vector<vector<ar>> E(n + 1);
	vector<vector<pair<int, long long>>> adj(n + 1);
	
	for(int i = 0;i < m;i++){
		int a, b, c, p;
		cin >> a >> b >> c >> p;
		E[a].push_back({b, c, p});
		E[b].push_back({a, c, p});
		adj[a].emplace_back(b, p);
		adj[b].emplace_back(a, p);
	}
	
	for(int i = 1;i <= n;i++){
		map<int, ll> S;
		for(auto [node, col, price] : E[i]){
			S[col] += price;
		}
		for(auto [node, col, price] : E[i]){
			adj[i].emplace_back(node, S[col] - price);
		}
	}
	
	auto Do = [&](int src, vector<long long> &d)->void{
      fill(d.begin(), d.end(), inf);
      vector<bool> in_Q(n + 1);
      d[src] = 0;
      priority_queue<pair<long long, int>> pq;
      pq.push({0, src});
      while(!pq.empty()){
			auto [_, node] = pq.top();		
			pq.pop();
			if(in_Q[node]) continue;
			in_Q[node] = 1;
			for(auto [to, cost] : adj[node]){
				if(d[node] + cost < d[to]){
					d[to] = d[node] + cost;
					pq.push({-d[to], to});
				}
			}
	   }
	};
	
	vector<long long> D(n + 1);
	Do(1, D);
	
	cout << (D[n] == inf ? -1 : D[n]) << '\n';
	
	return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 452 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 2 ms 660 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15320 KB Output is correct
2 Correct 21 ms 7256 KB Output is correct
3 Correct 65 ms 23504 KB Output is correct
4 Correct 32 ms 10456 KB Output is correct
5 Incorrect 231 ms 37212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 452 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 2 ms 660 KB Output isn't correct
10 Halted 0 ms 0 KB -