{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n\u003cdiv id\u003d\"problem-body\"\u003e\n \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\r\nMathJax.Hub.Config({\r\n tex2jax: {\r\n inlineMath: [[\u0027$\u0027,\u0027$\u0027], [\u0027\\\\(\u0027,\u0027\\\\)\u0027]],\r\n skipTags: [\"script\",\"noscript\",\"style\",\"textarea\",\"code\"]\r\n }\r\n});\r\n\u003c/script\u003e\n \u003cscript src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e\n \u003cp align\u003d\"justify\"\u003eMột nhóm chuột thí nghiệm đang được huấn luyện để thoát khỏi mê cung. Mê cung được tạo thành từ các ô, và mỗi ô được kết nối với một số ô khác. Tuy nhiên, có những chướng ngại vật trên đường đi giữa các ô và do đó có một thời gian phạt để vượt qua đường đi. Ngoài ra, một số đường đi cho phép chuột đi một chiều, nhưng không đi theo chiều ngược lại.\u003c/p\u003e\n \u003cp align\u003d\"justify\"\u003eGiả sử tất cả chuột bây giờ đã được huấn luyện và, khi được đặt trong một ô bất kỳ trong mê cung, chúng sẽ đi theo một con đường dẫn chúng đến ô thoát trong thời gian tối thiểu.\u003c/p\u003e\n \u003cp align\u003d\"justify\"\u003eChúng tôi sẽ tiến hành thí nghiệm sau: một con chuột được đặt trong mỗi ô của mê cung và một bộ đếm thời gian ngược được bắt đầu. Khi bộ đếm thời gian dừng lại, chúng tôi đếm số chuột đã thoát khỏi mê cung.\u003c/p\u003e\n \u003ch3\u003eVấn đề\u003c/h3\u003e\n \u003cp align\u003d\"justify\"\u003eViết một chương trình, với mô tả về mê cung và thời gian giới hạn, dự đoán số lượng chuột sẽ thoát khỏi mê cung. Giả sử rằng không có chỗ hẹp nào trong mê cung, tức là tất cả các ô đều có chỗ cho một số lượng chuột tùy ý.\u003c/p\u003e\n \u003ch3\u003eĐầu vào\u003c/h3\u003e\n \u003cp align\u003d\"justify\"\u003eCác ô của mê cung được đánh số từ $1, 2, \\ldots, N$, nơi $N$ là tổng số ô. Bạn có thể giả sử rằng $N \\le 100$.\u003c/p\u003e\n \u003cp align\u003d\"justify\"\u003eBa dòng đầu tiên chứa $N$, số lượng ô trong mê cung, $E$, số lượng ô thoát, và giá trị khởi đầu $T$ cho bộ đếm thời gian ngược (trong một đơn vị thời gian tùy ý).\u003c/p\u003e\n \u003cp align\u003d\"justify\"\u003eDòng thứ tư chứa số $M$ kết nối trong mê cung, và được theo sau bởi $M$ dòng, mỗi dòng chỉ định một kết nối với ba số nguyên: hai số ô $a$ và $b$ (trong phạm vi $1, \\ldots, N$) và số đơn vị thời gian cần để đi từ $a$ đến $b$.\u003c/p\u003e\n \u003cp align\u003d\"justify\"\u003eLưu ý rằng mỗi kết nối chỉ một chiều, tức là, chuột không thể đi từ $b$ đến $a$ trừ khi có một dòng khác chỉ định đường đi đó. Cũng lưu ý rằng thời gian cần thiết để đi trong mỗi hướng có thể khác nhau.\u003c/p\u003e\n \u003ch3\u003eĐầu ra\u003c/h3\u003e\n \u003cp align\u003d\"justify\"\u003eĐầu ra bao gồm một dòng duy nhất với số lượng chuột đã đạt đến ô thoát $E$ trong tối đa $T$ đơn vị thời gian.\u003c/p\u003e\n \u003ch3\u003eVí dụ\u003c/h3\u003e\n \u003cdiv\u003e\n \u003ctable class\u003d\"vjudge_sample\"\u003e\n \u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n \u003c/thead\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\n \u003cpre\u003e4 \r\n2 \r\n1\r\n8\r\n1 2 1\r\n1 3 1\r\n2 1 1\r\n2 4 1\r\n3 1 1\r\n3 4 1\r\n4 2 1\r\n4 3 1\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\n \u003cpre\u003e3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}}]}