← 返回题目列表

Codeforces · 360/E

E. Levko 和游戏

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

Levko非常喜欢他所在城市的体育寻路比赛。为了提高自己的表现,列夫科利用业余时间进行练习。练习就是一场游戏。

城市由 n 个交叉路口组成,由 m + k 个有向道路连接。两条或多条道路可以连接同一对交叉路口。此外,可以有从交叉路口通向其自身的道路。

Levko 和 Zenyk 正在玩游戏。首先 Levko 站在路口 s1 上,Zenyk 站在路口 s2 上。他们都想到达交叉路口 f。做得更快的人获胜。如果他们同时到达,则比赛以平局结束。根据协议,两名玩家同时开始并以相同的速度移动。

Levko非常想赢。他知道城里所有道路的长度。他还知道,如果他向政府付费,他可以改变某些道路的长度(总共有 k 条这样的道路)。因此,政府可以将第 i 条道路的长度更改为段 [li, ri](包括边界)中的任何整数值。列夫科想知道他是否可以重建道路以赢得比赛,如果他不能获胜,他是否可以希望平局。

您应该考虑到两名玩家都发挥最佳状态。保证我们可以从交点 s1 和 s2 到达交点 f。

输入

第一行包含三个整数 n、m 和 k (1 ≤ n, m ≤ 104, 1 ≤ k ≤ 100)。第二行包含三个整数 s1、s2 和 f(1 ≤ s1、s2、f ≤ n)。

接下来的 m 行包含 Levko 无法更改的道路的描述。每行包含三个整数ai、bi和ci(1≤ai,bi≤n,1≤ci≤109),表示从路口ai到路口bi的一条道路,长度为ci。

接下来的 k 行包含 Levko 可以更改的道路的描述。每行包含四个整数ai,bi,li和ri(1≤ai,bi≤n,1≤li≤ri≤109),代表从路口ai到路口bi的一条道路,Levko可以在限制[li,ri]内设置道路的长度。

考虑编号从 1 到 n 的所有交叉点。保证可以从路口 s1 和 s2 到达路口 f。

输出

如果 Levko 可以赢得这场比赛,则在第一行打印字符串“WIN”(不带引号);如果 Levko 可以以平局结束比赛,则打印字符串“DRAW”(不带引号);如果他肯定输了,则打印“LOSE”(不带引号)。

如果答案是“获胜”或“平局”,则在第二行打印 k 个空格分隔的整数 — Levko 按其在输入中出现的顺序设置的道路长度。

示例

输入 #1

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

输出 #1

WIN
1 1 3

输入 #2

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

输出 #2

DRAW
1 1 2

输入 #3

5 4 2
1 2 5
1 3 3
1 4 4
2 3 2
2 4 3
3 5 1 5
4 5 4 7

输出 #3

LOSE