|
| 入口的选择 Time Limit:1000MS Memory Limit:32768K Description: Zeism玩的赛车游戏中,有一种树形的赛道。树根表示赛道的终点,任何一个叶子结点表示一个赛道的入口,其余的结点都是中转站。如下图所示:在这种赛道中,Zeism可以选择A,B,C三个入口中的任意一个。为了赢得比赛,Zeism需要选择一条总路程最短的路线。Zeism发现,每个入口都存在一条到终点的最短路,因此,他需要做出的选择就是:选择哪个入口? Input: 输入数据是一条赛道。第一行N表示其后有N行数据。赛道的终点用字母T表示。赛道的入口和中转站用一个大写字母表示,且不会重名。输入数据的每一行由2个大写字母和一个正整数组成:U V D。表示站点U到站点V的路程为D公里。输入数据处理到文件结尾,并且保重数据的合法性。 Output: 输出数据包括入口和最短路程。如果存在多个最短路程相等的入口,请输出字母顺序最前的入口。 Sample Input: 2 T A 3 T B 2 Sample Output: B 2 |
题目解析:求从A B C 三个结点到达终点的最短路径,最简单就是采用深度优先搜索,搜索出所有可能到达终点的路径,从而求出最短路程。
代码:
#include<iostream>
#include<string>
#include <algorithm>
using namespace std;
//从某一点出发,搜索是否到达终点,如果到达返回到达该点的长度,否则返回从该点出发到达终点的最短长度
int souso(int map[26][26],int pre,intbegin,int sum){
intmin=1000000;
inttemp;
if(begin==('T'-65)){
returnsum;
}
for(inti=0;i<26;i++){
if(pre!=i&&map[begin][i]>0){
temp=souso(map,begin,i,sum+map[begin][i]);
if(temp<min)min=temp;
}
}
returnmin;
}
int main(){
intn,d,a,b,c,min;
charu,v,temp;
//保存各个节点的距离,如果为0表示未联通
int map[26][26];
while(cin>>n){
for(inti=0;i<26;i++){
for(int j=0;j<26;j++){
map[i][j]=0;
}
}
for(int i=0;i<n;i++){
cin>>u;
cin>>v;
cin>>d;
map[u-65][v-65]=d;
map[v-65][u-65]=d;
}
a=souso(map,-1,0,0);
b=souso(map,-1,1,0);
c=souso(map,-1,2,0);
min=a;
temp='A';
if(b<min){
min=b;
temp='B';
}
if(c<min) {
min=c;
temp='C';
}
cout<<temp<<""<<min<<endl;
}
return0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)