记录编号	45552	评测结果	AAAAAAAAA
题目名称	工程规划	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2012-10-24 15:19:33	内存使用	2.05 MiB

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 5000 + 10, INF = 100000;
int n, m, u[N], v[N], w[N], f[N], g[N];
bool Yakusoku() {
    bool l = 1;
    while(l) { l = 0;
        for(int i=1; i<=m; i++) {
            if(f[u[i]] - f[v[i]] > w[i])
                f[u[i]] = f[v[i]] + w[i], l = 1;
            if(g[u[i]] - g[v[i]] > w[i])
                g[v[i]] = g[u[i]] - w[i], l = 1;
            if(g[u[i]] > f[u[i]] || g[v[i]] > f[v[i]])
                return false;
        }
    } return true;
}
int main() {
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++)
        scanf("%d %d %d", u+i, v+i, w+i);
    for(int i=2; i<=n; i++)
        f[i] = INF, g[i] = -INF;
    f[1] = g[1] = 0;
    if(Yakusoku()) {
        int d = *min_element(g+1, g+n+1);
        for(int i=1; i<=n; i++)
            printf("%d\n", g[i] - d);
    } else printf("NO SOLUTION\n");
    return 0;
}