JOI 2022 - School Road
Xem PDFĐất nước Hải Ly có \(N\) thành phố, đánh số từ \(1\) đến \(N\), và \(M\) con đường, đánh số từ \(1\) đến \(M\). Đường \(i\) nối hai chiều giữa thành phố \(A_i\) và \(B_i\), có độ dài \(C_i\). Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua một số con đường.
Hải ly Bitaro sống ở thành phố \(1\) và học ở thành phố \(N\). Cậu thường đến trường theo một lộ trình cố định có độ dài \(L\), trong đó \(L\) là khoảng cách ngắn nhất từ thành phố \(1\) đến thành phố \(N\).
Hôm nay trời đẹp, Bitaro muốn đi đường vòng về nhà: từ thành phố \(N\) về thành phố \(1\) theo một lộ trình dài hơn \(L\). Vì dễ chán, cậu không muốn ghé cùng một thành phố nhiều lần. Do đó, trên đường về, cậu không được ghé một thành phố quá một lần và không được quay ngược lại giữa đường.
Cho thông tin về các thành phố và con đường, hãy xác định có tồn tại đường vòng từ trường về nhà thỏa mãn yêu cầu hay không.
Dữ liệu vào
Đọc từ đầu vào chuẩn, tất cả các giá trị đều là số nguyên:
N M
A_1 B_1 C_1
A_2 B_2 C_2
...
A_M B_M C_M
Dữ liệu ra
In 1 nếu tồn tại lộ trình từ trường về nhà dài hơn \(L\) mà không ghé thành phố nào quá một lần. Nếu không, in 0.
Ràng buộc
- \(2 \le N \le 100\,000\).
- \(1 \le M \le 200\,000\).
- \(1 \le A_i<B_i \le N\) \((1 \le i \le M)\).
- \(1 \le C_i \le 10^9\) \((1 \le i \le M)\).
- Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua một số con đường.
Chấm điểm
- \(7\) điểm: \(M \le 40\)
- \(15\) điểm: \(N \le 18\)
- \(23\) điểm: \(M-N \le 13\)
- \(35\) điểm: Với ba thành phố đôi một khác nhau \(a,b,c\) bất kỳ, tồn tại một lộ trình từ \(a\) đến \(c\) không đi qua \(b\).
- \(20\) điểm: Không có giới hạn bổ sung.
Ví dụ
Ví dụ 1
Input
4 4
1 2 1
1 3 2
2 4 4
3 4 3Output
0Giải thích
Khoảng cách ngắn nhất từ nhà ở thành phố \(1\) đến trường ở thành phố \(4\) là \(5\). Có hai lộ trình về nhà không lặp thành phố:
- Đi các đường \(3 \to 1\), qua các thành phố \(4 \to 2 \to 1\), dài \(5\).
- Đi các đường \(4 \to 2\), qua các thành phố \(4 \to 3 \to 1\), dài \(5\).
Không có lộ trình dài hơn \(5\), nên in 0. Ví dụ thỏa mãn mọi nhóm.
Ví dụ 2
Input
4 4
1 2 1
1 3 3
2 4 4
3 4 3Output
1Giải thích
Khoảng cách ngắn nhất vẫn là \(5\). Hai lộ trình không lặp thành phố là:
- Đi các đường \(3 \to 1\), qua các thành phố \(4 \to 2 \to 1\), dài \(5\).
- Đi các đường \(4 \to 2\), qua các thành phố \(4 \to 3 \to 1\), dài \(6\).
Có lộ trình dài hơn \(5\), nên in 1. Ví dụ thỏa mãn mọi nhóm.
Ví dụ 3
Input
3 4
1 2 1
1 2 2
1 3 3
1 3 3Output
0Giải thích
Ví dụ này thỏa mãn các nhóm \(1,2,3,5\).
Ví dụ 4
Input
4 5
1 2 1
1 3 2
2 4 4
3 4 3
2 3 1Output
1Giải thích
Ví dụ này thỏa mãn mọi nhóm.
Ví dụ 5
Input
12 17
2 4 656247308
4 6 106088453
1 5 754343261
9 12 497827261
3 8 759830309
3 4 61084725
1 6 324702188
3 6 415317430
7 12 846175092
5 8 278621369
1 10 891247646
10 12 755236904
6 8 511967203
5 6 597197970
1 7 800309458
7 9 348347831
10 11 134217757Output
0Giải thích
Ví dụ này thỏa mãn các nhóm \(1,2,3,5\).
Nguồn
JOI Open Contest 2022, JCIOI. Bản dịch tiếng Việt theo CC BY-SA 4.0.
Kỳ thi:
- JOI 2022 - Open Contest (3 Tháng bảy, 2022)
Bình luận