ZOJ Problem Set - 2027
Travelling Fee
Time Limit: 1 Second
Memory Limit: 32768 KB
Samball is going to travel in the coming vacation. Now it's time to make a plan. After choosing the destination city, the next step is to determine the travel route. As this poor guy has just experienced a tragic lost of money, he really has limited amount of money to spend. He wants to find the most costless route. Samball has just learned that the travel company will carry out a discount strategy during the vacation: the most expensive flight connecting two cities along the route will be free. This is really a big news.
Now given the source and destination cities, and the costs of all the flights, you are to calculate the minimum cost. It is assumed that the flights Samball selects will not have any cycles and the destination is reachable from the source.
Input The input contains several test cases, each begins with a line containing names of the source city and the destination city. The next line contains an integer m (<=100), the number of flights, and then m lines follow, each contains names of the source city and the destination city of the flight and the corresponding cost. City names are composed of not more than 10 uppercase letters. Costs are integers between 0 to 10000 inclusively. Process to the end of file.
Output For each test case, output the minimum cost in a single line.
Sample Input
HANGZHOU BEIJING 2 HANGZHOU SHANGHAI 100 SHANGHAI BEIJING 200
Sample Output
100
Author: CHEN, Shunbao
Source:
ZOJ Monthly, November 2003
Submit
Status
/*
用disjkstra算法将两点之间的所有路径求出，并且将所有所有路径中权值最大的那条边减去。然后再在这些减去最大权值的 路径中找出一条最短的路径输出 //1854878 2009-05-05 09:33:44 Accepted 2027 C++ 0 348 Wpl Wpl08，06，03,20:38
*/
#include #include
#define
MAX 202
using
namespace
std;
struct
node {
string
str;
int
num; }city[
201
];
//
用于存放城市编号和名称的结构体
int
edges[MAX][MAX],dist[MAX],path[MAX];
//
edges是图的邻接矩阵，dist存出发点到所有点的路径长度
bool
s[MAX];
void
dijkstra(
int
start,
int
end,
int
n)
//
s是标志，防止最短边的重复选取；path中存放的路径
{
int
i,j,k,min,maxTrip,maxValue,pre,tempValue; maxValue
=-
1
;
//
记录任意一条相通的路径中权值最大那个边的权值
maxTrip
=
2000000000
;
//
记录最小的花费
for
(i
=
1
;i
<=
n;i
++
)
//
初始化
{ s[i]
=
false
; dist[i]
=
edges[start][i]; path[i]
=
start; }
if
(dist[end]
!=-
1
)
//
如果两个边直接连通
{ printf(
"
0\n
"
);
return
; } s[start]
=
true
;
//
dist[start]=-1;
for
(i
=
1
;i { min
=
100002
;
for
(j
=
1
;j
<=
n;j
++
)
//
选出一条最短的边，并且这条边不会重复选取
{
if
(
!
s[j]
&&
dist[j]
=
0
) { min
=
dist[j]; k
=
j; } } s[k]
=
true
;
for
(j
=
1
;j
<=
n;j
++
) {
if
(s[j]
||
edges[k][j]
==-
1
)
continue
;
if
(dist[j]
>
dist[k]
+
edges[k][j]
||
dist[j]
==-
1
) { dist[j]
=
dist[k]
+
edges[k][j]; path[j]
=
k; }
if
(dist[end]
!=-
1
)
//
如果从出发点和终点形成一条可通的路径
{
int
bb
=
end;
//
记录每一条边的终点
pre
=
path[bb];
//
记录每一条边的起点
do
{ tempValue
=
edges[bb][pre];
//
进行临时记忆这条路径上的一个权值
if
(tempValue
>
maxValue) maxValue
=
tempValue; bb
=
pre; pre
=
path[pre]; }
while
(pre
!=
start);
if
(edges[bb][start]
>
maxValue)
//
最后一条边没有在do循环中做，要特殊对待
maxValue
=
edges[bb][start];
if
(maxTrip
>
dist[j]
-
maxValue) maxTrip
=
dist[j]
-
maxValue; dist[end]
=-
1
;
//
进行一次统计后将这条路径再次设置为不通
maxValue
=-
1
;
//
maxValue的值一定要变，这点很重要
} } } printf(
"
%d\n
"
,maxTrip); }
int
main() {
string
str1,str2,str3,str4;
int
m,zz,z,i,j,x,y,a,b,mm;
while
(cin
>>
str1
>>
str2) { z
=
0
; mm
=
1
; cin
>>
m;
for
(i
=
1
;i
<=
200
;i
++
) city[i].num
=
0
;
for
(i
=
1
;i
<=
200
;i
++
)
for
(j
=
1
;j
<=
200
;j
++
) edges[i][j]
=-
1
; cin
>>
str3
>>
str4
>>
zz; city[z].str
=
str3; city[z
++
].num
=
mm
++
; city[z].str
=
str4; city[z
++
].num
=
mm
++
; edges[
1
][
2
]
=
edges[
2
][
1
]
=
zz;
for
(i
=
1
;i { cin
>>
str3
>>
str4
>>
zz;
for
(j
=
0
;j {
if
(str3
==
city[j].str)
//
如果存在
{ x
=
city[j].num;
//
用x记下它的编号
break
;
//
统计出来后跳出循环就好
} }
if
(j
>=
z)
//
如果已存城市名字中不存在刚输入的城市名字，那么就将其存入下一个结构体中
{ city[z].str
=
str3;
//
加下其名字
city[z
++
].num
=
mm
++
;
//
为其编号
x
=
mm
-
1
;
//
因为mm已经加1所以减一才是它应有的编号
}
for
(j
=
0
;j {
if
(str4
==
city[j].str)
//
如果存在
{ y
=
city[j].num;
//
用y记下它的编号
break
;
//
统计出来后跳出循环就好
} }
if
(j
>=
z)
//
如果已存城市名字中不存在刚输入的城市名字，那么就将其存入下一个结构体中
{ city[z].str
=
str4;
//
加下其名字
city[z
++
].num
=
mm
++
;
//
为其编号
y
=
mm
-
1
;
//
因为mm已经加1所以减一才是它应有的编号
} edges[x][y]
=
edges[y][x]
=
zz;
//
将值存入矩阵
}
for
(i
=
0
;i {
if
(str1
==
city[i].str) { a
=
city[i].num;
break
; } }
for
(i
=
0
;i {
if
(str2
==
city[i].str) { b
=
city[i].num;
break
; } }
//
cout< dijkstra(a,b,z);
}
return
0
; }
转载于:https://www.cnblogs.com/forever4444/archive/2009/05/08/1452866.html
相关资源：数据结构—成绩单生成器
