| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14374 | 2024_DS_Summer_Lab16_Score Game |
|
Description
You play a game consisting of n vertices and m edges. The edge is directed.
Your initial score is 0, and edge i increases your score by xi (xi may be both positive or negative). You may go through an edge several times.
Your task is to walk from vertices 1 to vertices n. What is the maximum score you can get?
Input
The first input line has two integers n and m: the number of vertices and edges. The vertices are numbered 1, 2, ..., n.
Then, there are m lines describing the edges. Each line has three integers a, b and x: the edge connect vertices a to b, and it increases your score by x.
You can assume that it is possible to get from room 1 to vetices n.
Output
Print one integer: the maximum score you can get.
However, if you can get an arbitrarily large score, print −1.