{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e阿里这学期选修了《计算机组织与体系结构》课程。他了解到指令之间可能存在依赖关系,比如WAR(读后写)、WAW、RAW。\u003cbr\u003e如果两条指令之间的距离小于安全距离,就会产生冒险,可能导致错误的结果。因此,我们需要设计特殊的电路来消除冒险。然而,解决这个问题最简单的方法就是添加气泡(无用操作),也就是浪费时间,以确保两条指令之间的距离不小于安全距离。\u003cbr\u003e两条指令之间的距离定义为它们开始时间的差值。\u003cbr\u003e现在我们有许多指令,我们知道指令之间的依赖关系和安全距离。我们还有一个非常强大的CPU,拥有无限数量的核心,所以你可以同时运行尽可能多的指令,而且CPU的速度非常快,只需要1纳秒就可以完成任何指令。\u003cbr\u003e你的任务是重新安排指令,使CPU以最短的时间完成所有指令。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入包括多个测试用例。\u003cbr\u003e第一行包含两个整数N、M(N ≤ 1000,M ≤ 10000),表示有N条指令和M个依赖关系。\u003cbr\u003e接下来的M行,每行包含三个整数X、Y、Z,表示X和Y之间的安全距离为Z,Y应该在X之后运行。指令编号从0到N - 1。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"输出一个整数,表示CPU运行所需的最短时间。\u003cbr\u003e"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003cpre\u003e5 2\r\n1 2 1\r\n3 4 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"\u003cbr\u003e在第1纳秒,执行指令0、1和3;\u003cbr\u003e在第2纳秒,执行指令2和4。\u003cbr\u003e因此答案应为2。\u003cbr\u003e"}}]}