- Time limit: 1.00 s
- Memory limit: 128 MB
Bittimaassa on kaupunkia, joiden välillä on tietä. Yksi kaupungeista on pääkaupunki.
Tehtäväsi on laskea, montako erilaista tapaa on poistaa joukko teitä niin, että etäisyydet pääkaupungista kaikkiin muihin kaupunkeihin säilyvät samoina.
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua ja : kaupunkien määrä ja teiden määrä. Kaupungit on numeroitu , ja kaupunki on pääkaupunki.
Sitten syötteessä on riviä, joista jokainen kuvaa yhden tien. Jokaisella rivillä on kolme kokonaislukua , ja : tie on kaupunkien ja välillä ja sen pituus on . Kaikki tiet ovat kaksisuuntaisia.
Voit olettaa, että kaikkien kaupunkien välillä on jokin reitti.
Tuloste
Tulosta yksi kokonaisluku: vastaus tehtävään. Koska vastaus voi olla suuri, tulosta se modulo .
Rajat
Esimerkki
Syöte:
4 5 1 2 5 1 3 1 1 4 7 2 4 3 3 4 2
Tuloste:
4
Selitys: voit säilyttää kaikki tiet, poistaa 3-painoisen tien, poistaa 7-painoisen tien tai poistaa 3-painoisen ja 7-painoisen tien.