No.848 Friendly Trip
タグ : / 解いたユーザー数 164
作問者 :
chocorusk
/ テスター :
tempura_pp
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もしくは右上の雲マークをクリックしてアカウントを作成してください。