{"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当YY还是个男孩,LMY还是个女孩时,他们在GD团队为全国信息学奥林匹克竞赛(NOI)进行训练。一天,GD团队的教练,郭教授,要求他们解决以下最短路径问题。\u003cbr\u003e给定一个带权重的有向多重图G。该有向多重图有以下两种操作:\u003cbr\u003e(1) 在图中标记一个顶点。\u003cbr\u003e(2) 通过标记的顶点找到两个顶点之间的最短路径。\u003cbr\u003eLMY第一次面对这样的问题,感到非常紧张。这时,YY决定帮助LMY分析最短路径问题。在YY的帮助下,LMY立刻解决了问题,非常钦佩YY。从那时起,每当LMY遇到问题,她总是叫YY来帮她分析问题。当然,YY非常乐意帮助LMY。最终,众所周知,YY和LMY成为了编程爱好者。\u003cbr\u003e你能解决这个最短路径问题吗?\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入包含多个测试用例。对于每个测试用例,第一行包含三个整数N、M和Q,其中N是给定图中的顶点数,N≤300;M是弧的数量,M≤100000;Q是操作数,Q≤100000。所有顶点依次编号为0、1、2,直到N - 1。最初所有顶点都未标记。接下来的M行中,每行描述一条弧,由三个整数(x,y,c)表示:起始顶点(x),终止顶点(y)和弧的权重(c)。(c \u003e 0) 然后,接下来的Q行描述一个操作,其中操作“0 x”表示标记顶点x,操作“1 x y”找到通过标记的顶点之间的最短路径长度。两个连续测试用例之间有一个空行。\u003cbr\u003e输入以包含N \u003d M \u003d Q \u003d 0 的行表示输入结束。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"每个测试用例以单独一行的形式以“Case #:”开头,其中#是从1开始的案例编号。\u003cbr\u003e对于操作“0 x”,如果顶点x已被标记,则输出“ERROR!在点x处”。\u003cbr\u003e对于操作“1 x y”,如果顶点x或顶点y未被标记,则输出“ERROR!在路径x到y处”;如果y无法通过标记的顶点从x到达,则输出“无此路径”;否则输出最短路径的长度。格式如示例输出所示。\u003cbr\u003e两个连续测试用例之间有一个空行。\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 10 10\r\n1 2 6335\r\n0 4 5725\r\n3 3 6963\r\n4 0 8146\r\n1 2 9962\r\n1 0 1943\r\n2 1 2392\r\n4 2 154\r\n2 2 7422\r\n1 3 9896\r\n0 1\r\n0 3\r\n0 2\r\n0 4\r\n0 4\r\n0 1\r\n1 3 3\r\n1 1 1\r\n0 3\r\n0 4\r\n0 0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1:\r\nERROR! At point 4\r\nERROR! At point 1\r\n0\r\n0\r\nERROR! At point 3\r\nERROR! At point 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}