Flights 2

AtCoder

IDagc072_e

Time2000ms

Memory256MB

Difficulty—

Japan has $N$ airports numbered $1, 2, \dots, N$. AtCoder Airlines operates $M$ directed flight routes in Japan, numbered $1, 2, \dots, M$. Route $j$ goes from airport $A_j$ to airport $B_j$ and costs $C_j \times F$ yen. Flying with AtCoder Airlines earns “miles.” You start with $0$ miles. Taking route $j$ once grants $C_j$ miles. At airport $i$, you can exchange miles for money at the rate $R_i$ yen per mile. Because of the constraint $0 \le R_i \le F-1$, endless profit cycles are impossible. You can exchange a non-integral amount of miles or have a non-integral amount of money, but you cannot have a negative amount of miles or money. What is the minimum initial amount of money in yen needed to fly from airport $1$ to airport $N$? Solve $\mathrm{TESTCASES}$ test cases. ## Constraints * $1 \le \mathrm{TESTCASES} \le 40\,000$ * $2 \leq N \leq 400$ * $1 \leq M \leq N \times (N-1)$ * $1 \leq F \leq 100$ * $1 \leq A_j \leq N$ * $1 \leq B_j \leq N$ * $A_j \neq B_j$ * $(A_1, B_1), (A_2, B_2), \dots, (A_M, B_M)$ are all different. * $1 \le C_j \le 100$ * $0 \le R_i \le F-1$ * It is possible to go from airport $1$ to airport $N$. * The sum of $N^2$ over all test cases is at most $160\,000$. * All input values are integers. ## Input The input is given from Standard Input in the following format, where $\mathrm{case}_k$ represents the $k$\-th test case: $\mathrm{TESTCASES}$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_{\mathrm{TESTCASES}}$ Each test case is given in the following format: $N$ $M$ $F$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_M$ $B_M$ $C_M$ $R_1$ $R_2$ $\cdots$ $R_N$ [samples]

Samples

Input #1

Output #1

146

If you start with $146$ yen, you can go from airport $1$ to airport $3$:

1.  Take route $1$ to go from airport $1$ to airport $2$. You now have $146-70=76$ yen, and get $7$ miles.
2.  At airport $2$, exchange $7$ miles for $14$ yen. You now have $76+14=90$ yen.
3.  Take route $2$ to go from airport $2$ to airport $3$. You now have $90-90=0$ yen, and get $9$ miles.

If you start with less than $146$ yen, you cannot go to airport $3$.

Input #2

Output #2

106

If you start with $106$ yen, you can go from airport $1$ to airport $4$:

1.  Take route $1$ to go from airport $1$ to airport $2$. You now have $106-70=36$ yen, and get $7$ miles.
2.  Take route $3$ to go from airport $2$ to airport $3$. You now have $36-10=26$ yen, and get $1$ mile.
3.  At airport $3$, exchange $8$ miles for $72$ yen. You now have $26+72=98$ yen.
4.  Take route $4$ to go from airport $3$ to airport $2$. You now have $98-10=88$ yen, and get $1$ mile.
5.  At airport $2$, exchange $1$ mile for $2$ yen. You now have $88+2=90$ yen.
6.  Take route $2$ to go from airport $2$ to airport $4$. You now have $90-90=0$ yen, and get $9$ miles.

If you start with less than $106$ yen, you cannot go to airport $4$.

Input #3

1
7 8
100
3 2 81
3 4 42
1 6 97
4 5 42
4 1 59
6 3 34
5 3 68
2 7 47
0 58 37 10 89 16 0

Output #3

16354.2758620689655172413793103448275862068965

API Response (JSON)

{
  "problem": {
    "name": "Flights 2",
    "description": {
      "content": "Japan has $N$ airports numbered $1, 2, \\dots, N$. AtCoder Airlines operates $M$ directed flight routes in Japan, numbered $1, 2, \\dots, M$. Route $j$ goes from airport $A_j$ to airport $B_j$ and costs",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc072_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Japan has $N$ airports numbered $1, 2, \\dots, N$. AtCoder Airlines operates $M$ directed flight routes in Japan, numbered $1, 2, \\dots, M$. Route $j$ goes from airport $A_j$ to airport $B_j$ and costs...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments