#3285. 游览
-
ID: 3285
传统题
2000ms
512MiB
尝试: 4
已通过: 0
难度: 10
上传者:
18779948623
游览
说明
顺利通过了黄药师的考验，下面就可以尽情游览桃花岛了！
<button class="btn btn-primary btn-circle btn-xs" style="--tw-border-spacing-x:0;--tw-border-spacing-y:0;--tw-translate-x:0;--tw-translate-y:0;--tw-rotate:0;--tw-skew-x:0;--tw-skew-y:0;--tw-scale-x:1;--tw-scale-y:1;--tw-pan-x:;--tw-pan-y:;--tw-pinch-zoom:;--tw-scroll-snap-strictness:proximity;--tw-gradient-from-position:;--tw-gradient-via-position:;--tw-gradient-to-position:;--tw-ordinal:;--tw-slashed-zero:;--tw-numeric-figure:;--tw-numeric-spacing:;--tw-numeric-fraction:;--tw-ring-inset:;--tw-ring-offset-width:0px;--tw-ring-offset-color:#fff;--tw-ring-color:rgb(59 130 246 / .5);--tw-ring-offset-shadow:0 0 #0000;--tw-ring-shadow:0 0 #0000;--tw-shadow:0 0 #0000;--tw-shadow-colored:0 0 #0000;--tw-blur:;--tw-brightness:;--tw-contrast:;--tw-grayscale:;--tw-hue-rotate:;--tw-invert:;--tw-saturate:;--tw-sepia:;--tw-drop-shadow:;--tw-backdrop-blur:;--tw-backdrop-brightness:;--tw-backdrop-contrast:;--tw-backdrop-grayscale:;--tw-backdrop-hue-rotate:;--tw-backdrop-invert:;--tw-backdrop-opacity:;--tw-backdrop-saturate:;--tw-backdrop-sepia:;display:inline-flex;flex-shrink:0;cursor:pointer;user-select:none;flex-wrap:wrap;align-items:center;justify-content:center;border-width:initial;border-style:none;border-color:initial;transition-property:color, background-color, border-color, text-decoration-color, fill, stroke, opacity, box-shadow, transform, filter, backdrop-filter, -webkit-backdrop-filter;transition-timing-function:cubic-bezier(0, 0, 0.2, 1);transition-duration:0.2s;border-radius:9999px;height:1.5rem;padding:0px;min-height:1.5rem;font-size:0.75rem;line-height:1em;gap:0.5rem;font-weight:600;animation:button-pop var(--animation-btn, .25s) ease-out;text-transform:var(--btn-text-case, uppercase);--tw-border-opacity:1;--tw-bg-opacity:1;--tw-text-opacity:1;outline-color:hsl(var(--p) / 1);width:1.5rem;"><svg viewbox="0 0 24 24" role="presentation" style="width:0.9rem;height:0.9rem;"><path d="M16,12A2,2 0 0,1 18,10A2,2 0 0,1 20,12A2,2 0 0,1 18,14A2,2 0 0,1 16,12M10,12A2,2 0 0,1 12,10A2,2 0 0,1 14,12A2,2 0 0,1 12,14A2,2 0 0,1 10,12M4,12A2,2 0 0,1 6,10A2,2 0 0,1 8,12A2,2 0 0,1 6,14A2,2 0 0,1 4,12Z" style="fill:currentcolor;"></path></svg></button>
你要从桃花岛的西头开始一直玩到东头，然后在东头的码头离开。可是当你游玩了一次后，发现桃花岛的景色实在是非常的美丽！！！于是你还想乘船从桃花岛东头的码头回到西头，再玩一遍，但是桃花岛有个规矩：你可以游览无数遍，但是每次游玩的路线不能完全一样。
我们把桃花岛抽象成了一个图，共 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个点代表路的相交处，<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>m 条边表示路，边是有向的（只能按照边的方向行走），且可能有连接相同两点的边。输入保证这个图没有环，而且从西头到东头至少存在一条路线。两条路线被认为是不同的当且仅当它们所经过的路不完全相同。
你的任务是：把所有不同的路线游览完一共要花多少时间？
输入格式
第一行为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>5</mn></mrow></semantics></math>5 个整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo separator="true">,</mo><mi>�</mi><mo separator="true">,</mo><mi>�</mi><mo separator="true">,</mo><mi>�</mi><mo separator="true">,</mo><msub><mi>�</mi><mn>0</mn></msub></mrow></semantics></math>n,m,s,t,t0，分别表示点数，边数，岛西头的编号，岛东头的编号（编号是从 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn></mrow></semantics></math>1 到 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n）和你乘船从岛东头到西头一次的时间。 以下 m 行，每行 3 个整数 x,y,t，表示从点 x 到点 y 有一条行走耗时为 t 的路。 每一行的多个数据之间用一个空格隔开。输出格式
假设总耗时为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mi>�</mi><mi>�</mi><mi>�</mi><mi>�</mi></mrow></semantics></math>total，则输出 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mi>�</mi><mi>�</mi><mi>�</mi><mi>�</mi><mtext> </mtext><mtext> </mtext><mo lspace="0.22em" rspace="0.22em"><mrow style="--tw-border-spacing-x:0;--tw-border-spacing-y:0;--tw-translate-x:0;--tw-translate-y:0;--tw-rotate:0;--tw-skew-x:0;--tw-skew-y:0;--tw-scale-x:1;--tw-scale-y:1;--tw-pan-x:;--tw-pan-y:;--tw-pinch-zoom:;--tw-scroll-snap-strictness:proximity;--tw-gradient-from-position:;--tw-gradient-via-position:;--tw-gradient-to-position:;--tw-ordinal:;--tw-slashed-zero:;--tw-numeric-figure:;--tw-numeric-spacing:;--tw-numeric-fraction:;--tw-ring-inset:;--tw-ring-offset-width:0px;--tw-ring-offset-color:#fff;--tw-ring-color:rgb(59 130 246 / .5);--tw-ring-offset-shadow:0 0 #0000;--tw-ring-shadow:0 0 #0000;--tw-shadow:0 0 #0000;--tw-shadow-colored:0 0 #0000;--tw-blur:;--tw-brightness:;--tw-contrast:;--tw-grayscale:;--tw-hue-rotate:;--tw-invert:;--tw-saturate:;--tw-sepia:;--tw-drop-shadow:;--tw-backdrop-blur:;--tw-backdrop-brightness:;--tw-backdrop-contrast:;--tw-backdrop-grayscale:;--tw-backdrop-hue-rotate:;--tw-backdrop-invert:;--tw-backdrop-opacity:;--tw-backdrop-saturate:;--tw-backdrop-sepia:;border-color:currentcolor;"><mi mathvariant="normal" style="--tw-border-spacing-x:0;--tw-border-spacing-y:0;--tw-translate-x:0;--tw-translate-y:0;--tw-rotate:0;--tw-skew-x:0;--tw-skew-y:0;--tw-scale-x:1;--tw-scale-y:1;--tw-pan-x:;--tw-pan-y:;--tw-pinch-zoom:;--tw-scroll-snap-strictness:proximity;--tw-gradient-from-position:;--tw-gradient-via-position:;--tw-gradient-to-position:;--tw-ordinal:;--tw-slashed-zero:;--tw-numeric-figure:;--tw-numeric-spacing:;--tw-numeric-fraction:;--tw-ring-inset:;--tw-ring-offset-width:0px;--tw-ring-offset-color:#fff;--tw-ring-color:rgb(59 130 246 / .5);--tw-ring-offset-shadow:0 0 #0000;--tw-ring-shadow:0 0 #0000;--tw-shadow:0 0 #0000;--tw-shadow-colored:0 0 #0000;--tw-blur:;--tw-brightness:;--tw-contrast:;--tw-grayscale:;--tw-hue-rotate:;--tw-invert:;--tw-saturate:;--tw-sepia:;--tw-drop-shadow:;--tw-backdrop-blur:;--tw-backdrop-brightness:;--tw-backdrop-contrast:;--tw-backdrop-grayscale:;--tw-backdrop-hue-rotate:;--tw-backdrop-invert:;--tw-backdrop-opacity:;--tw-backdrop-saturate:;--tw-backdrop-sepia:;border-color:currentcolor;">m</mi><mi mathvariant="normal" style="--tw-border-spacing-x:0;--tw-border-spacing-y:0;--tw-translate-x:0;--tw-translate-y:0;--tw-rotate:0;--tw-skew-x:0;--tw-skew-y:0;--tw-scale-x:1;--tw-scale-y:1;--tw-pan-x:;--tw-pan-y:;--tw-pinch-zoom:;--tw-scroll-snap-strictness:proximity;--tw-gradient-from-position:;--tw-gradient-via-position:;--tw-gradient-to-position:;--tw-ordinal:;--tw-slashed-zero:;--tw-numeric-figure:;--tw-numeric-spacing:;--tw-numeric-fraction:;--tw-ring-inset:;--tw-ring-offset-width:0px;--tw-ring-offset-color:#fff;--tw-ring-color:rgb(59 130 246 / .5);--tw-ring-offset-shadow:0 0 #0000;--tw-ring-shadow:0 0 #0000;--tw-shadow:0 0 #0000;--tw-shadow-colored:0 0 #0000;--tw-blur:;--tw-brightness:;--tw-contrast:;--tw-grayscale:;--tw-hue-rotate:;--tw-invert:;--tw-saturate:;--tw-sepia:;--tw-drop-shadow:;--tw-backdrop-blur:;--tw-backdrop-brightness:;--tw-backdrop-contrast:;--tw-backdrop-grayscale:;--tw-backdrop-hue-rotate:;--tw-backdrop-invert:;--tw-backdrop-opacity:;--tw-backdrop-saturate:;--tw-backdrop-sepia:;border-color:currentcolor;">o</mi><mi mathvariant="normal" style="--tw-border-spacing-x:0;--tw-border-spacing-y:0;--tw-translate-x:0;--tw-translate-y:0;--tw-rotate:0;--tw-skew-x:0;--tw-skew-y:0;--tw-scale-x:1;--tw-scale-y:1;--tw-pan-x:;--tw-pan-y:;--tw-pinch-zoom:;--tw-scroll-snap-strictness:proximity;--tw-gradient-from-position:;--tw-gradient-via-position:;--tw-gradient-to-position:;--tw-ordinal:;--tw-slashed-zero:;--tw-numeric-figure:;--tw-numeric-spacing:;--tw-numeric-fraction:;--tw-ring-inset:;--tw-ring-offset-width:0px;--tw-ring-offset-color:#fff;--tw-ring-color:rgb(59 130 246 / .5);--tw-ring-offset-shadow:0 0 #0000;--tw-ring-shadow:0 0 #0000;--tw-shadow:0 0 #0000;--tw-shadow-colored:0 0 #0000;--tw-blur:;--tw-brightness:;--tw-contrast:;--tw-grayscale:;--tw-hue-rotate:;--tw-invert:;--tw-saturate:;--tw-sepia:;--tw-drop-shadow:;--tw-backdrop-blur:;--tw-backdrop-brightness:;--tw-backdrop-contrast:;--tw-backdrop-grayscale:;--tw-backdrop-hue-rotate:;--tw-backdrop-invert:;--tw-backdrop-opacity:;--tw-backdrop-saturate:;--tw-backdrop-sepia:;border-color:currentcolor;">d</mi></mrow></mo><mtext> </mtext><mn>10000</mn></mrow></semantics></math>total mod10000 的值（<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mi>�</mi><mi>�</mi><mi>�</mi><mi>�</mi></mrow></semantics></math>total 对 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>10000</mn></mrow></semantics></math>10000 取余）。样例
3 4 1 3 7
1 2 5
2 3 7
2 3 10
1 3 1556提示
