#include <bits/stdc++.h>
#define mt make_tuple
#define mp make_pair
#define pb push_back
#define printv(v) for (int i = 0; i < v.size(); i++) cout << v[i] << " "; cout << "\n"
using namespace std;
struct SegTree
{
int n;
vector<int> data;
SegTree(int n) : n(n), data(2*n, 0) {}
void build(const vector<int>& cost_sums)
{
for (int i = 0; i < n; i++)
data[i+n] = cost_sums[i];
for (int i = n-1; i > 0; i--)
data[i] = data[i<<1] + data[i<<1|1];
}
int get(int l, int r)
{
int res = 0;
for (l+=n, r+=n; l < r; l>>=1,r>>=1)
{
if (l&1) res += data[l++];
if (r&1) res += data[--r];
}
return res;
}
};
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>> og(n); // Graph with only paved roads
vector<tuple<int, int, int>> edges; // Only unpaved roads
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
a--, b--;
if (c)
{
edges.pb(mt(a, b, c));
}
else
{
og[a].pb(b);
og[b].pb(a);
}
}
vector<int> mapping(n);
int node = 0;
while (og[node].size() == 2) node++;
mapping[node] = 0;
for (int j = 1, i = og[node][0], prev = node; j < n; j++)
{
mapping[i] = j;
if (og[i].size() == 1)
break;
int _new = (og[i][0] == prev) ? og[i][1] : og[i][0];
prev = i;
i = _new;
}
vector<vector<pair<int, int>>> forward_edges(n);
int total_cost = 0;
for (auto [a, b, c] : edges)
{
a = mapping[a], b = mapping[b];
if (a > b)
swap(a, b);
if ((b-a)&1)
total_cost += c;
else
forward_edges[a].pb(mp(b, c));
}
vector<int> cost_sums(n);
for (int i = 0; i < n; i++)
{
int sum = 0;
for (auto [_, c] : forward_edges[i])
sum += c;
cost_sums[i] = sum;
}
SegTree st(n);
st.build(cost_sums);
vector<int> dp(n, 1e8);
dp[0] = 0;
for (int i = 0; i < n-1; i++)
{
if (i != n-1)
dp[i+1] = min(dp[i+1], dp[i] + cost_sums[i]);
for (auto [r, c] : forward_edges[i])
dp[r] = min(dp[r], dp[i] + st.get(i, r) - c);
}
cout << (total_cost + dp[n-1]) << "\n";
}
Compilation message
training.cpp: In function 'int main()':
training.cpp:70:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
70 | for (auto [a, b, c] : edges)
| ^
training.cpp:84:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
84 | for (auto [_, c] : forward_edges[i])
| ^
training.cpp:96:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
96 | for (auto [r, c] : forward_edges[i])
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
244 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
