UOJ Logo Universal Online Judge

UOJ

#32. 【UR #2】跳蚤公路

附件下载 统计

跳蚤国由 $n$ 个城市组成,编号为 $1$ 到 $n$。

跳蚤国有 $m$ 条连接城市的单向高速公路。经过高速公路当然是要收费的 —— 每条高速公路都有一个过路费 $w$ (货币单位为跳蚤币),司机每次经过这条公路时都需要缴纳 $w$ 跳蚤币。特别地,过路费可以是负的,这表示司机每次经过这条公路时政府都会给 $-w$ 跳蚤币的补贴。

随着时代发展,跳蚤国王认为原有的高速公路规划已经不符合国情了。于是他根据交通拥堵情况把每条公路染成了红、绿、白三色之一,然后他会小心地选定一个数 $x$,再把每条红色公路的过路费涨 $x$ 跳蚤币,把每条绿色公路的过路费降 $x$ 跳蚤币,而白色公路的过路费不变。

虽然让绿色公路降过路费是好事,但是如果过路费降得太厉害,某个跳蚤司机就可以从 $1$ 号城市出发在城市间转悠,最后停在某个城市 $v$,数一下自己的钱包发现自己竟然赚钱了。如果赚的钱超过 $10^{100}$ 跳蚤币,则我们称这样的路径为发财路径

现在跳蚤国王还不太确定 $x$ 的取值应该是多少,他当然讨厌这种丑陋的靠补贴费发财的行为。于是他希望助手伏特对于 $v = 1 \dots n$,求出使得不存在从 $1$ 号城市出发到 $v$ 号城市结束的发财路径的整数 $x$ 的个数。

除此之外,$x$必须介于 $-10^{30}$ 到 $10^{30}$之间。

伏特当然知道怎么做啦!但是他想考考你。

输入格式

第一行包括两个正整数 $n$ 和 $m$。表示跳蚤国的城市数和高速公路数。

接下来 $m$ 行,每行四个用空格隔开的整数 $v, u, w, s$ ($1 \leq v, u \leq n$, $s \in \{-1, 0, 1\}$),表示一条从 $v$ 号城市向 $u$ 号城市的过路费为 $w$ 的单向高速公路。如果 $s = 1$ 则为红色,$s = 0$ 则为白色,$s = -1$ 则为绿色。

输出格式

输出 $n$ 行,第 $i$ 行包含一个整数表示 $v = i$ 时满足条件的 $x$ 的个数。如果 $x$ 的个数超过 $10^{18}$个,请输出 $-1$。

C/C++ 输入输出 long long 时请用 %lld。C++ 可以直接使用 cin/cout 输入输出。

样例一

input

5 6
1 2 7 0
1 4 3 -1
2 5 4 0
2 3 1 -1
2 3 -3 1
3 2 1 0

output

-1
1
1
-1
1

explanation

对于任何一个 $x$ 都找不到从 $1$ 出发到 $1, 4$ 结束的发财路径。

只有当 $x = 2$ 时,才找不到从 $1$ 出发到 $2, 3, 5$ 结束的发财路径。

样例二

input

12 15
1 2 1 0
1 4 1000000000 0
1 6 2 0
2 3 2 0
4 4 -2 1
4 4 10 -1
4 3 1000000000 0
6 7 -5 0
7 8 10 -1
8 6 10 -1
7 9 6 -1
9 10 2 1
10 11 3 1
11 9 5 1
12 12 -233 0

output

-1
-1
9
9
-1
-1
-1
-1
11
11
11
-1

explanation

对于 $3, 4$ 号城市,无法发财的 $x$ 的取值范围为 $[2, 10]$。

对于 $6, 7, 8$ 号城市,无法发财的 $x$ 的取值范围为 $[-10^{30}, 7.5]$。

对于 $9, 10, 11$ 号城市,无法发财的 $x$ 的取值范围为 $\left[-\frac{10}{3}, 7.5\right]$。由于要求是整数,所以只有介于 $-3$ 到 $7$ 的整数满足条件,共 $11$ 个 $x$ 的取值。

特别注意 $12$ 号城市,虽然不断地从 $12$ 号城市出发再回 $12$ 号城市就可以发财,但是 $1$ 号城市无法到达 $12$ 号城市,所以所有 $x$ 都满足条件。

样例三

见样例数据下载。去掉所有的自环后图中不存在环。

样例四

见样例数据下载。

限制与约定

测试点编号 $n$的规模 $m$的规模 其他
1$n \leq 9$$m \leq 20$
2$n \leq 40$$m \leq 1500$
3
4
5
6$n \leq 100$$m \leq 10000$保证去掉所有的自环后图中不存在环
7
8
9
10

保证对于每条边,$\left|w \right| \leq 10^9$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载