## 入口的选择 ~~~ 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; } ~~~