← 返回题目列表

AtCoder · pakencamp_2019_day4_e

E. 对于 IOI

中文机器翻译题面 查看原题

配点: 100 点

問題文

今年是20XX年。 IOI(International Olympiad in Iconolam)现在是一项家喻户晓、家喻户晓的比赛,每年夏季和冬季举行。

20XX IOI将在Kclc王国举行。作为IOI王国委员会管理员的Square决定考虑这次游览的路线。

IOI中可以使用的Kclc王国土地是 他们之间有 N 。 M 一条真正的道路贯穿其中。在陆地上 1 到 N ,在路上 1 到 M 。其中 2 你还可以通过多条道路在陆地之间旅行。

道路 i 是土地 A_i 和土地 B_i 双向相连,行车时间与夏季大致相同。 S_i,冬天的时候 W_i 。 土地从

土地 1 开始 通往 N 之路 游览路线 我们称之为 。

在夏季或冬季至少一个季节满足以下条件的游览路线有多少条?

  • 没有一条游览路线需要更少的总旅行时间。

答案可能非常大,所以 请输出除以10^9+7 后的余数。

制約

  • 所有输入均为整数
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)
  • 哪个 2 也可以通过多条道路进入土地。
  • 1 \leq S_i, W_i \leq 10^9\ (1 \leq i \leq M)

部分点

该问题分为多个子任务,如果您正确回答了该子任务的所有测试用例,则视为您正确回答了该子任务。

提交的源代码的分数是您正确回答的子作业分数的总和。

  1. (5 点) M=N-1 满意。
  2. (15 点) N \leq 10 满意。
  3. (20 分) 任意 1 \leq i \leq M ,S_i = W_i 满意。
  4. (35 点) N \leq 1000 满意。
  5. (25 分) 没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1 S_1 W_1
:
A_M B_M S_M W_M

出力

计算至少一个季节(夏季或冬季)满足条件的游览路线数量。 10^9+7 后的余数。


入力例 1

4 8
1 2 3 2
1 3 2 1
1 3 3 1
2 2 1 1
2 3 1 1
2 3 2 1
2 4 1 2
3 4 2 4

出力例 1

6

以下游览路线符合条件: 6 有两个。 它按照

  • 道路 1, 7 的顺序传递。夏季和冬季均满足条件。 它按顺序经历
  • 道路 2, 5, 7 的顺序传递。夏季和冬季均满足条件。 它按顺序经历
  • 道路 2, 6, 7 。仅在冬季才能满足该条件。
  • 道路 3, 5, 7 。仅在冬季才能满足该条件。
  • 道路 3, 6, 7 。仅在冬季才能满足该条件。
  • 道路 2, 8 按此顺序传递。仅在夏季满足该条件。

入力例 2

4 5
1 2 3 6
2 3 1 2
3 4 2 5
1 3 5 3
2 4 4 2

出力例 2

2

入力例 3

20 77
9 16 65551022 36847141
4 8 169905126 234841269
8 18 61782163 101070315
8 9 763292109 656192270
1 18 76893781 240632078
3 19 601597138 476288881
5 19 595403102 581080612
3 6 980642190 183697163
6 9 663706146 95151932
11 18 679581087 523262198
12 16 293035618 152800086
3 7 814717585 273291118
1 2 853500661 870996856
2 3 526446904 394372085
2 9 75096934 115522990
4 9 599545324 421351001
1 13 282807719 968765138
6 15 458441410 364130005
1 4 178858403 334122865
4 4 242708006 509603317
8 13 368467895 338762793
13 17 697663167 640858525
11 20 238453071 271106570
2 17 126970225 114980011
14 18 279244522 277866206
11 20 238453071 271106570
5 20 714162258 622887639
4 12 694170286 610998228
9 16 65551022 36847141
15 15 341887831 393369008
3 8 311942139 377343175
1 8 15111618 99281596
2 4 674642258 536873991
2 16 9545912 78675849
1 8 15111618 99281596
12 20 121899250 49599586
14 20 638789636 516502562
5 17 699705205 614143827
7 13 480049964 311871500
9 14 422265424 394103067
7 10 230695689 160298785
2 20 141427278 488804437
9 16 65551022 36847141
2 4 746378429 794786225
1 13 684196511 438044389
9 19 97765056 384638724
8 14 599920464 622509237
16 20 446862361 693104823
2 20 141427278 250722614
17 18 964998636 785624956
11 20 238453071 271106570
1 3 327053757 476624771
1 5 327955959 908911545
3 11 429421111 769824924
7 19 113311100 202997763
13 18 205913938 237692478
1 17 980470886 985976867
3 12 545974932 468496322
6 19 312631863 292591718
11 15 651379358 427422180
3 8 311942139 377343175
8 17 965359268 886695271
3 20 667874182 518095908
12 17 107442197 40855774
2 10 321338667 306331990
4 13 103949316 103921524
9 10 246241733 165856762
7 14 406719380 271697772
7 8 747746065 755010172
1 9 778403727 755473866
8 17 965359268 886695271
5 11 475709187 351781069
8 11 751809642 869885243
5 19 595403102 581080612
19 20 118759156 41807027
3 19 646592547 476288881
3 12 850613737 468496322

出力例 3

190