## 入口的選擇 ~~~ 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; } ~~~