C17E:Walking Around the Country
- 总时间限制:
- 3000ms
- 内存限制:
- 262144kB
- 描述
Jason lives in a country consists of N cities, numbered from 1 to N. Any two cities are connected by two directed roads. Walking on each road takes exactly one day. There are M places of interests in the country, numbered from 1 to M. Each place i locates on the road from city s[i] to city t[i]. Jason is planning a trip. For each place i, he wants to visit at least k[i] times. He also wants to finish his trip as soon as possible because he has a lot of homework to do. He can start from any city. Could you help him arrange a travel route?
- 输入
- The first line contains an integer T (1 <= T <= 15), indicating the number of test cases.
For each test case:
The first line contains two integers N and M (1 <= N <= 100,000, 1 <= M <= 300,000), indicating there are N cities and M places of interests in the country.
Then M lines follow, the i-th line contains three integers s[i], t[i], and k[i] (1 <= s[i],t[i] <= N, s[i] ≠ t[i], 1 <= k[i] <= 300,000, ∑k[i] <= 300,000), indicating place i locates on the road from city s[i] to city t[i], and should be visited at least k[i] times.
It is guaranteed that no two places locate on the same road.
- 输出
- For each test case:
The first line contains one integer t, indicating the minimum time Jason has to spend.
The second line contains t+1 integers, separated by spaces, indicating the city numbers that Jason is going to travel in order. If there are several possible answers, output any one of them.
- 样例输入
1
4 3
1 2 3
3 4 2
4 3 2
- 样例输出
10
1 2 3 4 3 4 3 1 2 1 2
- 全局题号
- 15050
- 添加于
- 2017-05-21
- 提交次数
- 220
- 尝试人数
- 14
- 通过人数
- 9
