Background

This is an output-only problem.

Problem Description

This year happens to be Youth Day on May 4th. On such a great day, the young explorer Niuniu leads his scientific expedition team to explore a primeval forest.

Before the expedition starts, Niuniu obtains a map of the forest. There are $n$ gathering points in the forest, numbered from $1$ to $n$. Between these gathering points, there are $m$ paths, numbered from $1$ to $m$. Each path starts at one gathering point and ends at another gathering point.

To improve the expedition efficiency, Niuniu divides his team into $p$ squads, and each squad can independently complete some tasks. They agree to start from the gathering point numbered $S$ and finally meet at the gathering point numbered $T$. During the expedition, they will face many difficulties. For example, team members can slowly descend from the top of a cliff to the bottom, but cannot climb directly from the bottom to the top. Therefore, all paths in the input are one-way.

When a squad moves along a path, it records various information and testdata on that path. However, some paths need to be opened up by the expedition team themselves. Opening a path consumes certain materials and produces some cost. Due to limited equipment, the equipment assigned to each squad may be different, so on some difficult paths, some squads may be unable to pass because they lack enough equipment. However, by allocating equipment reasonably, Niuniu ensures that every squad can successfully reach the gathering point numbered $T$.

After all squads arrive at point $T$ and meet, Niuniu will aggregate all information and testdata. The total value of this information and testdata is the total revenue of this scientific expedition. If multiple squads pass through the same path, since the data they record about this path is duplicated, its value is counted only once. The cost spent on opening paths is the total expenditure of this expedition. Similarly, even if multiple squads pass through the same path that needs to be opened, this path only needs to be opened once.

Now, Niuniu hopes to design reasonable action routes for his $p$ squads so that the value of total revenue minus total expenditure is maximized.

Input Format

The input files expedition1.in~expedition10.in are provided in the problem directory.

For each input dataset:

The first line contains $5$ integers $n, m, p, S, T$, with meanings as described above.

The next $2m$ lines describe the paths, with every two lines describing one path.

On the first line of each path, there are three integers $u, v, w$, indicating that the path starts at $u$ and ends at $v$. If $w < 0$, it means the data value on this path is $w$, and it does not need to be opened. If $w \leq 0$, it means the data value on this path is $0$, and the cost to open it is $-w$.

On the second line of each path, the first integer is $k$, indicating the number of squads that cannot pass this path. Then follow $k$ distinct integers, indicating the indices of these $k$ squads.

Output Format

The output files expedition1.out~expedition10.out are provided in the problem directory.

For each input dataset, you need to output $p$ lines in order. The $i$-th line describes the action sequence of squad $i$.

The first number on each line is $k$, indicating how many paths this squad has traveled in total. Then follow $k$ numbers, indicating the indices of the paths this squad travels through in order when going from $S$ to $T$.

4 4 2 1 4
1 3 3
1 2
1 2 5
0
2 3 -2
1 1 
3 4 1
0

2 1 4
3 2 3 4

Hint

Explanation for Sample 1

There are $4$ gathering points and $4$ paths on the map. The paths that squad $1$ can pass are $1, 2, 4$, and the paths that squad $2$ can pass are $2, 3, 4$. In the end, squad $1$ passes paths $1, 4$ in order, and squad $2$ passes paths $2, 3, 4$ in order. The total revenue obtained is $3 + 5 + 1 = 9$. The total expenditure is $2$. The value of total revenue minus total expenditure is $9 - 2 = 7$.

Scoring

Each test point is scored independently. For each test point, you may also receive partial credit.

For each test point, we provide $10$ scoring parameters $a_1, a_2, a_3, \dots, a_9, a_{10}$. If your output is invalid, you get $0$ points. Otherwise, in your solution, if the expedition’s total revenue is $w_{user}$, and there exists a largest $i$ such that $w_{user} \geq a_{i}$, then you get $i$ points.

All scoring parameter files expedition1.ans~expedition10.ans are provided in the problem directory. Each scoring parameter file has $10$ lines. On the $i$-th line there is a non-negative integer indicating $a_i$.

Input Data Download

Download link

Translated by ChatGPT 5