{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e \u0026nbsp;\u003c/p\u003e \n\u003cdiv\u003e\n \u0026nbsp;\n\u003c/div\u003e \n\u003cp\u003e \u003cimg align\u003d\"right\" height\u003d\"300\" src\u003d\"http://uva.onlinejudge.org/external/109/p10917.jpg\" width\u003d\"400\"\u003e\u003c/p\u003e \n\u003ch2\u003e Problem C: 傲娇的尿神\u003c/h2\u003e \n\u003cp\u003e gbn最近打算穿过一个森林,但是他比较傲娇,于是他决定只走一些特殊的道路,他打算只沿着满足如下条件的(A,B)道路走:存在一条从B出发回家的路,比所有从A出发回家的路径都短。你的任务是计算一共有多少条不同的回家路径。其中起点的编号为1,终点的编号为2.\u003c/p\u003e \n\u003ch3\u003e Input\u003c/h3\u003e \n\u003cp\u003e \u003cspan\u003e多组数据输入,每组数据第一行输入n\u003c/span\u003e,m(1\u0026lt;\u003dn\u0026lt;\u003d1000)\u003cspan\u003e表示点的数目和边的数目,点的编号为1\u003c/span\u003e~\u003cspan\u003en,接下来m行每行输入3个数a\u003c/span\u003e,b,\u003cspan\u003ec表示有一条双向道路连接a\u003c/span\u003e,\u003cspan\u003eb长度为c(1\u003c/span\u003e\u0026lt;\u003dc\u0026lt;\u003d10^\u003cspan\u003e6)\u003c/span\u003e当n\u003d0的时候结束输入\u003c/p\u003e \n\u003ch3\u003e Output\u003c/h3\u003e \n\u003cp\u003e 对于每组数据输出一个数表示路径的条数,保证答案不超过(2^\u003cspan\u003e31)-1。\u003c/span\u003e\u003c/p\u003e \n\u003ch3\u003e Sample Input\u003c/h3\u003e \n\u003cpre\u003e\r\n5 6\r\n1 3 2\r\n1 4 2\r\n3 4 3\r\n1 5 12\r\n4 2 34\r\n5 2 24\r\n7 8\r\n1 3 1\r\n1 4 1\r\n3 7 1\r\n7 4 1\r\n7 5 1\r\n6 7 1\r\n5 2 1\r\n6 2 1\r\n0\r\n\u003c/pre\u003e \n\u003ch3\u003e Output for Sample Input\u003c/h3\u003e \n\u003cpre\u003e\r\n2\r\n4\r\n\u003c/pre\u003e \n\u003cp\u003e (apologies to) \u003ci\u003eRichard Krueger\u003c/i\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cbr\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cbr\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cbr\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003e"}}]}