Nội dung Bài tập
- Mã:
- ACM2016_North_H
- Tên:
- Beautiful trails (ACM 2016 Miền Bắc)
- Dạng thi:
- acm
- Thang điểm:
- 1 điểm
- Giới hạn thời gian:
- 10 giây
- Giới hạn bộ nhớ:
- 64 MB
- Được tạo bởi:
- admin
In the highlands in north Vietnam, there are remoted areas where ethnic groups are living. Although the living condition here is far from sufficient but the people are living a peaceful and enjoyable life with the fresh air and the beautiful scenery. There are N villages in this area (numbered 1 to N), connected by M one-way trails (numbered 1 to M). There is no trail connect a village to itself. Between two villages, there might be multiple trails connect them. Along each trail, there are different types of wildflowers. The flowers along each trail is represent with a string consists of uppercase letters. A trail from village x to village y has the wildflowers ABCD means that it has length 4 and the wild flower you will see when trekking along this trail is A, B, C, D in that order. If there is a trail from village y to village z and it has the wildflowers XYZ, if you trek along village 1 to village 2 and on to village 3 then the wildflowers you see is ABCDXYZ (in that order).
Mark loves trekking and he knows these areas very well. He is wonder if there exist 2 different trekking path where the wildflowers he sees along the trails are exactly the same. These 2 paths does not need to have the same starting and ending village. If they exist, what is the minimal length?
Input
The input starts with the number of test - T (T ≤ 300). Then T tests follow:• The first line is the number of villages N (N ≤ 50) and the number of trails M (M ≤ 1000).• The next M lines consists of 2 integers x, y (1 ≤ x, y ≤ N) and a string S representing a trail. The length of S does not exceed 20.
Output
For each test, print the minimal length of 2 similar trekking paths or print -1 if there is no such pair of paths.Sample
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
THPT_NK_DEQUY
#include <iostream>using namespace std;bool isValidTime(int hour, int minute, int se...