問題一覧 > 通常問題

No.848 Friendly Trip

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 164
作問者 : chocorusk / テスター : tempura_pp
お気に入りにしたユーザー ProblemId : 2711 / 自分の提出
問題文最終更新日: 2019-07-04 18:16:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 217 (順位表) の他の問題:

Problem Statement

Yukiotoko and Yukionna have come on a trip to the country of yuki. The country of yuki consists of $N$ towns numbered $1, 2, \ldots , N$ and $M$ roads numbered $1, 2, \ldots, M$. Road $i$ ($1\leq i\leq M$) bidirectionally connects town $a_i$ and town $b_i$. The $2$ people walk at the same speed, and walking along road $i$ takes $c_i$ minutes for each of the $2$ people. However, they cannot turn back partway along a road.

The $2$ people are initially in town $1$, where the airport is located, and they were planning to walk to the tourist attractions in town $P$ and town $Q$, but they realized that they must be back in town $1$ after $T$ minutes. So the $2$ people decided to act so that the following conditions are satisfied.

  • At least one of the $2$ people visits town $P$.
  • At least one of the $2$ people visits town $Q$.

However, the $2$ people are very close friends, so they want to spend as much time together as possible, with the $2$ people acting together. Find the maximum time during the $T$ minutes that the $2$ people can spend acting together.

Here, time during which the $2$ people are waiting at the same place also counts as time spent acting together.

Input

$N\ M\ P\ Q\ T$
$a_1\ b_1\ c_1$
$\ldots$
$a_M\ b_M\ c_M$

  • $3\leq N\leq 2000$
  • $2\leq M\leq 10^5$
  • $2\leq P < Q\leq N$
  • $1\leq T\leq 10^9$
  • $1\leq a_i < b_i\leq N$
  • $1\leq c_i\leq 10^9$
  • $(a_i, b_i)\neq (a_j, b_j)$ when $i\neq j$
  • Every town can be reached on foot from town $1$.
  • All input values are integers.

Output

Print, in minutes, the maximum time the $2$ people can spend acting together while satisfying the conditions in the problem statement. If the conditions cannot be satisfied no matter how they act, print $-1$.

Sample

Sample 1
Input
4 3 2 4 15
1 3 2
3 4 4
2 3 3
Output
7

For example, they can act as follows.

  • Yukiotoko moves through towns $1\to 3\to 2\to 3$, waits for $2$ minutes in town $3$, then returns to town $1$ and waits for $3$ minutes.
  • Yukionna moves through towns $1\to 3\to 4\to 3\to 1$ and waits for $3$ minutes in town $1$.

In this case, the time the $2$ people spend acting together is from $0$ minutes to $2$ minutes and from $10$ minutes to $15$ minutes, for a total of $7$ minutes. They may return to town $1$ earlier than $T$ minutes, in which case the time the $2$ people spend in town $1$ until $T$ minutes have passed also counts as time spent acting together.

Sample 2
Input
4 3 2 4 20
1 3 2
3 4 4
2 3 3
Output
20

The $2$ people can move together through towns $1\to 3\to 2\to 3\to 4\to 3\to 1$ and wait for $2$ minutes in town $1$.

Sample 3
Input
4 3 2 4 10
1 3 2
3 4 4
2 3 3
Output
-1

Sample 4
Input
5 5 2 5 12
2 4 1
3 5 5
1 3 1
2 5 10
1 4 1
Output
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。