CENTRE
View as PDFTheo thống kê cho biết mức độ tăng trưởng kinh tế của nước Peace trong năm ~2006~ rất đáng khả quan. Cả nước có tổng cộng ~N~ thành phố lớn nhỏ được đánh số tuần tự từ ~1~ đến ~N~ phát triển khá đồng đều. Giữa ~N~ thành phố này là một mạng lưới gồm ~M~ đường đi hai chiều, mỗi tuyến đường nối ~2~ trong ~N~ thành phố sao cho không có ~2~ thành phố nào được nối bởi quá ~1~ tuyến đường. Trong ~N~ thành phố này thì thành phố ~1~ và thành phố ~N~ là ~2~ trung tâm kinh tế lớn nhất nước và hệ thống đường đảm bảo luôn có ít nhất một cách đi từ thành phố ~1~ đến thành phố ~N~.
Tuy nhiên, cả ~2~ trung tâm này đều có dấu hiệu quá tải về mật độ dân số. Vì vậy, đức vua Peaceful quyết định chọn ra thêm một thành phố nữa để đầu tư thành một trung tâm kinh tế thứ ba. Thành phố này sẽ tạm ngưng mọi hoạt động thường nhật, cũng như mọi luồng lưu thông ra vào để tiến hành nâng cấp cơ sở hạ tầng. Nhưng trong thời gian sửa chữa ấy, phải bảo đảm đường đi ngắn nhất từ thành phố ~1~ đến thành phố ~N~ không bị thay đổi, nếu không nền kinh tế quốc gia sẽ bị trì trệ.
Vị trí và đường nối giữa ~N~ thành phố được mô tả như một đồ thị ~N~ đỉnh ~M~ cạnh. Hãy giúp nhà vua đếm số lượng thành phố có thể chọn làm trung tâm kinh tế thứ ba sao cho thành phố được chọn thỏa mãn các điều kiện ở trên
Input
Dòng đầu tiên ghi ~2~ số nguyên dương ~N~ và ~M~ là số thành phố và số tuyến đường.
Dòng thứ ~i~ trong số ~M~ dòng tiếp theo ghi ~3~ số nguyên dương ~x_{i}~, ~y_{i}~ và ~d_{i}~ với ý nghĩa tuyến đường thứ ~i~ có độ dài ~d_{i}~ và nối giữa ~2~ thành phố ~x_{i}~, ~y_{i}~.
Output
Dòng đầu tiên ghi số tự nhiên ~S~ là số lượng các thành phố có thể chọn làm trung tâm kinh tế thứ ba.
~S~ dòng tiếp theo, mỗi dòng ghi ~1~ số nguyên dương là số thứ tự của thành phố được chọn (In ra theo thứ tự tăng dần).
Sample Input
6 6
1 2 1
2 3 1
3 6 1
1 4 100
4 5 100
5 6 100
Sample Output
2
4
5
Note
Giới hạn
- ~2 \leq N \leq 30000~
- ~1 \leq M \leq 100000~
- ~1 \leq d_{i} \leq 1000~
Comments
I dont like british english
https://ideone.com/Qxf4Yf sao code nay cua toi bi WA 3 test 8->10 v a
https://ideone.com/mnd76W sao code nay ko AC duoc test cuoi vay moi nguoi ai giup em voi huhu
code bạn sửa như này nhé:
sao lại sửa thế hả bạn
vì số đường đi có thể rất lớn, vượt kiểu long long. nên bản chất bạn đang thực hiện phép hash tràn số để so sánh
cnt1[i] * cnt2[i]vớicnt1[n]. và vì đó là phép hash nên giá trị đã bị mod đi rồi, vì vậy việc so sánh dùng dấu < là không đúng, mặc dù về bản chất thì nó đúng.This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
Bài tập này đã được thêm test và chấm lại, nhiều bài nộp cũ đã không còn AC.
This comment is hidden due to too much negative feedback. Show it anyway.