#include <bits/stdc++.h>
using namespace std;
int const maxn = 1e5+1;
vector<int> ans;
vector<vector<array<int,2> > > adj(maxn);
int gazda[maxn],vred[maxn][2],k;
bool visited[maxn];
int niza[maxn];
void bfs(int g,int k)
{
int z = 0;
queue<array<int,2> > q;queue<int> zima;
q.push({g,k});
while (q.size())
{
int p = q.front()[0],x = q.front()[1];gazda[p] = g;
q.pop();
zima.push(p);
for (auto a: adj[p]){
if (visited[a[0]]){
if (vred[a[0]][0] + x != a[1]*2) z = -1e9;
continue;
}
visited[a[0]] = true;vred[a[0]][0] = a[1]*2 - x; z+= abs(vred[a[0]][0]);
q.push({a[0],vred[a[0]][0]});
}
}
if (z<niza[g] && z>= 0){
niza[g] = z;
while (zima.size())
{
int p = zima.front();
zima.pop();
vred[p][1] = vred[p][0];
}
}
}
int main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;for (int i=0;i<=n;i++) niza[i] = 1e9;
for (int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
for (k=0;k<=1000;k++)
{
memset(visited,0,sizeof(visited));
for (int i=1;i<=n;i++)
if (visited[i] == false) bfs(i,-500 + k);
}
for (int i=1;i<=n;i++)
if (niza[gazda[i]] == 1e9) {
cout<<"NO\n";
return 0;
}
cout<<"YES\n";
for (int i=1;i<=n;i++)
{
double d = vred[i][1];
cout<<d/2<<" ";
}
return 0;
}
# | 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... |