#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll BIG = 1234567891234567890;
vector<ll> min_cost;
vector<vector<pair<int, pair<ll, int>>>> adj; // {color, {cost, dest}}
vector<map<int, int>> ct;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
int lastUnique;
ll direct_robot(int n, vector<int> u, vector<int> v, vector<int> col, vector<ll> cost) {
int m = u.size();
lastUnique = m;
adj.resize(n);
ct.resize(n);
min_cost.resize(n, BIG);
for(int i = 0; i < m; i++) {
adj[u[i]].push_back({col[i], {cost[i], v[i]}});
adj[v[i]].push_back({col[i], {cost[i], u[i]}});
ct[u[i]][col[i]]++;
ct[v[i]][col[i]]++;
}
for(int i = 0; i < n; i++) {
sort(adj[i].begin(), adj[i].end());
for(int j = 0; j < adj[i].size(); j++) {
bool ok = false;
if(j == adj[i].size()-1) ok = true;
else if(adj[i][j].first != adj[i][j+1].first) ok = true;
if(ok) {
ll tot_cost = 0;
int k;
for(k = j-1; k >= 0; k--) {
if(adj[i][k].first != adj[i][j].first) break;
tot_cost += adj[i][k].second.first;
}
for(k = j-1; k >= 0; k--) {
if(adj[i][k].first != adj[i][j].first) break;
int u_node, v_node, u_cost, v_cost;
tie(u_cost, u_node) = adj[i][j].second;
tie(v_cost, v_node) = adj[i][k].second;
adj[v_node].push_back({lastUnique++, {tot_cost, u_node}});
}
adj[i][j].second.first = min((ll)adj[i][j].second.first, tot_cost);
}
}
}
pq.push({0, 0});
while(pq.size()) {
pair<ll, int> p = pq.top();
pq.pop();
ll curr_cost;
int curr_node;
tie(curr_cost, curr_node) = p;
if(min_cost[curr_node] != BIG) continue;
min_cost[curr_node] = curr_cost;
for(auto pa : adj[curr_node]) {
int next_node;
ll next_cost;
tie(next_cost, next_node) = pa.second;
next_cost += curr_cost;
if(min_cost[next_node] != BIG) continue;
pq.push({next_cost, next_node});
}
}
return (min_cost[n-1] == BIG ? -1 : min_cost[n-1]);
}
int main() {
int n, m;
cin >> n >> m;
vector<int> u(m), v(m), col(m);
vector<ll> cost(m);
for(int i = 0; i < m; i++) {
cin >> u[i] >> v[i] >> col[i] >> cost[i];
u[i]--;
v[i]--;
col[i]--;
}
cout << direct_robot(n, u, v, col, cost) << '\n';
}
Compilation message
Main.cpp: In function 'll direct_robot(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<long long int>)':
Main.cpp:28:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int j = 0; j < adj[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
Main.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | if(j == adj[i].size()-1) ok = true;
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
22168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
