# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
888064 | Macker | Training (IOI07_training) | C++17 | 4 ms | 856 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
int main()
{
int n, m; cin >> n >> m;
vector<vector<pair<int, int>>> adj(n);
vector<vector<pair<int, int>>> v(n);
vector<int> idx(n, -1);
int res = 0;
for (int i = 0; i < m; i++) {
int a, b, c; cin >> a >> b >> c; a--; b--;
adj[a].push_back({c, b});
adj[b].push_back({c, a});
}
int s;
for (int i = 0; i < n; i++)
{
sort(all(adj[i]));
if(adj[i].size() == 1 || adj[i][1].first != 0) s = i;
}
int par = s;
for (int i = 0; i < n; i++)
{
idx[s] = i;
for (auto &&j : adj[s]) {
if(j.first != 0 && idx[j.second] != -1){
if((i - idx[j.second]) % 2 == 1)
res += j.first;
else
v[i].push_back({j.first, idx[j.second]});
}
}
if(par != adj[s][0].second){
par = s;
s = adj[s][0].second;
}
else{
par = s;
s = adj[s][1].second;
}
}
vector<int> dp(n);
dp[0] = res;
for (int i = 1; i < n; i++) {
int sm = 0;
for (int j = 0; j < v[i].size(); j++) {
sm += v[i][j].first;
}
dp[i] = dp[i - 1] + sm;
for (int j = 0; j < v[i].size(); j++) {
int cur;
if(v[i][j].second == 0) cur = sm - v[i][j].first + res;
else cur = sm - v[i][j].first + dp[v[i][j].second];
for (int k = v[i][j].second + 1; k < i; k++) {
for (auto &&l : v[k])
cur += l.first;
}
dp[i] = min(dp[i], cur);
}
}
cout << dp[n - 1] << endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |