📄 b.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0044)http://plg.uwaterloo.ca/~acm00/020601/B.html -->
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=GB18030">
<META content="MSHTML 6.00.2900.2963" name=GENERATOR></HEAD>
<BODY text=#000000 bgColor=#ffffff><IMG src="B.files/trail.jpg" align=right>
<H2>Problem B: Jogging Trails</H2>Gord is training for a marathon. Behind his
house is a park with a large network of jogging trails connecting water
stations. Gord wants to find the shortest jogging route that travels along every
trail at least once.
<P>Input consists of several test cases. The first line of input for each case
contains two positive integers: <I>n <= 15</I>, the number of water stations,
and <I>m < 1000</I>, the number of trails. For each trail, there is one
subsequent line of input containing three positive integers: the first two,
between 1 and <I>n</I>, indicating the water stations at the end points of the
trail; the third indicates the length of the trail, in cubits. There may be more
than one trail between any two stations; each different trail is given only once
in the input; each trail can be travelled in either direction. It is possible to
reach any trail from any other trail by visiting a sequence of water stations
connected by trails. Gord's route may start at any water station, and must end
at the same station. A single line containing 0 follows the last test case.
<P>For each case, there should be one line of output giving the length of Gord's
jogging route.
<H3>Sample Input</H3><PRE>4 5
1 2 3
2 3 4
3 4 5
1 4 10
1 3 12
0
</PRE>
<H3>Output for Sample Input</H3><PRE>41
</PRE></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -