#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 2e5;
int n, m;
vector< pair<int, long double> > g[N+10];
int used[N+10];
long double cost[N+10];
long double sum;
void dfs(int v){
used[v] = 1;
sum+= cost[v];
for(auto [to, c] : g[v]){
if(used[to] == 0){
cost[to] = c - cost[v];
dfs(to);
}else{
}
}
}
main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
long double ans = 1e18;
cin >> n >> m;
for(int i = 0;i < m; i++){
int a, b, c; cin >> a >> b >> c;
g[a].push_back({b, (long double)c * 1.0});
g[b].push_back({a, (long double)c * 1.0});
}
vector<long double> how(n + 1);
for(int i = 1;i <= n; i++){
for(int j = 1;j <= n; j++) used[j] = 0;
sum = 0;
cost[i] = 0;
dfs(i);
int ok = 1;
for(int v = 1; v <= n && ok; v++){
for(auto [to, c] : g[v]){
if(cost[v] + cost[to] != c){
ok = 0;
break;
}
}
}
if(ans > sum && ok){
ans = sum;
for(int j = 1;j <= n; j++) how[j] = cost[j];
}
}
for(int i = 1;i <= n; i++){
for(int j = 1;j <= n; j++) used[j] = 0;
sum = 0;
cost[i] = 0.5;
dfs(i);
int ok = 1;
for(int v = 1; v <= n && ok; v++){
for(auto [to, c] : g[v]){
if(cost[v] + cost[to] != c){
ok = 0;
break;
}
}
}
if(ans > sum && ok){
ans = sum;
for(int j = 1;j <= n; j++) how[j] = cost[j];
}
}
// cout << ans << '\n';
if(ans >= 1e18){
cout << "NO";
return 0;
}
cout << "YES" << '\n';
for(int i = 1;i <= n; i++) cout << how[i] << ' ';
return 0;
}
Compilation message
Graph.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
28 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 2 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 3 |
Correct |
2 ms |
7512 KB |
answer = YES |
| 4 |
Correct |
1 ms |
7512 KB |
answer = NO |
| 5 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 6 |
Incorrect |
1 ms |
7512 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 2 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 3 |
Correct |
2 ms |
7512 KB |
answer = YES |
| 4 |
Correct |
1 ms |
7512 KB |
answer = NO |
| 5 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 6 |
Incorrect |
1 ms |
7512 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 2 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 3 |
Correct |
2 ms |
7512 KB |
answer = YES |
| 4 |
Correct |
1 ms |
7512 KB |
answer = NO |
| 5 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 6 |
Incorrect |
1 ms |
7512 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 2 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 3 |
Correct |
2 ms |
7512 KB |
answer = YES |
| 4 |
Correct |
1 ms |
7512 KB |
answer = NO |
| 5 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 6 |
Incorrect |
1 ms |
7512 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 2 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 3 |
Correct |
2 ms |
7512 KB |
answer = YES |
| 4 |
Correct |
1 ms |
7512 KB |
answer = NO |
| 5 |
Correct |
2 ms |
7516 KB |
answer = YES |
| 6 |
Incorrect |
1 ms |
7512 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
