Tokens re-collection

Tokens re-collection

测试数据来自 AOCode/1042

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P1042 Tokens re-collection

Problem Background

AppOfficer didn't run out of the maze. All his tokens were snatched by Cui2010. Now he wants to
get all his tokens back. Unfortunately, he can't.

Problem Statement

Now AppOfficer is trapped in a hole. He's at point \(1\). The exit is at point \(n\). His \(m\) tokens are placed in some parts of the hole. There are \(k\) edges. For each edge, there're three integers \(x\) \(y\) \(t\), means that he can go directly from point \(x\) to point \(y\) in \(t\) minutes. But he can't go from \(y\) to \(x\)! AppOfficer not only wants to get his tokens back, but also wants to escape the hole ASAP. So if he gets \(a\) tokens back, and he reaches point \(n\) in \(b\) minutes, he wants to minimize \((50-a) \times b\). Please tell him the product. If he cannot reach point n, print Czy you don't have force morality! Rat tail juice!.

Input

The first line includes three integers \(n\), \(m\), \(k\).
The second line includes \(m\) integers, they mean where AppOfficer's tokens are.
Next \(k\) lines, every line includes three integers \(x\), \(y\), \(t\), describing an edge.

Output

One integer, the product. Or Czy you don't have force morality! Rat tail juice!

Constraints

  • \( 1 \le n \le 10^5 \)
  • \( 1 \le m \le 50 \)
  • \( 1 \le k \le \displaystyle \min \left\{\frac {n \times (n+1)} {2}, 5 \times 10^5 \right\} \)
  • \( 1 \le x < y \le n \)
  • \( 1 \le t \le 10^4 \)

Samples

Input 1

3 1 3
2
1 2 1
2 3 3
1 3 3

Output 1

150

There're two kinds of ways to reach point \(n\).

  • \(1\Rightarrow2\Rightarrow3\) time: \(4\) , tokens: \(1\). So the product is \((50-1) \times 4 = 196 \)
  • \(1\Rightarrow3\) time: \(3\) , tokens: \(0\). So the product is \((50-0) \times 3 = 150\)

Input 2

3 2 1
2 3
1 2 1

Output 2

Czy you don't have force morality! Rat tail juice!

It's obvious that AppOfficer cannot escape the hole.

AOCode Rematch

未参加
状态
已结束
规则
OI
题目
5
开始于
2022-08-04 15:00
结束于
2022-08-04 18:00
持续时间
3.0 小时
主持人
参赛人数
4