題目描述
現在是晚餐時間,而母牛們在外面分散的牧場中。 農民約翰按響了電鈴,所以她們開始向谷倉走去。 你的工作是要指出哪只母牛會最先到達谷倉(在給出的測試數據中,總會有且只有一只最快的母牛)。 在擠奶的時候(晚餐前),每只母牛都在她自己的牧場上,一些牧場上可能沒有母牛。 每個牧場由一條條道路和一個或多個牧場連接(可能包括自己)。 有時，兩個牧場(可能是字母相同的)之間會有超過一條道路相連。 至少有一個牧場和谷倉之間有道路連接。 因此,所有的母牛最后都能到達谷倉,并且母牛總是走最短的路徑。 當然,母牛能向著任意一方向前進,并且她們以相同的速度前進。 牧場被標記為'a'..'z'和'A'..'Y',在用大寫字母表示的牧場中有一只母牛,小寫字母中則沒有。 谷倉的標記是'Z',注意沒有母牛在谷倉中。
注意'm'和'M'不是同一個牧場 否則錯誤 上面的意思是說：輸入數據中可能會同時存在M,m（郁悶ing)(PS:表郁悶…告訴我set of咋用就不郁悶了…)，比如
M a a m m z
輸入輸出格式
輸入格式：
?
第 1 行: 整數 P(1<= P<=10000),表示連接牧場(谷倉)的道路的數目。
第 2 ..P+1行: 用空格分開的兩個字母和一個整數:
被道路連接牧場的標記和道路的長度(1<=長度<=1000)。
?
輸出格式：
?
單獨的一行包含二個項目: 最先到達谷倉的母牛所在的牧場的標記,和這只母牛走過的路徑的長度。
?
輸入輸出樣例
輸入樣例#1：
5 A d 6 B d 3 C e 9 d Z 8 e Z 3
輸出樣例#1：
B 11
說明
翻譯來自NOCOW
USACO 2.4
代碼
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<map> 8 #define MAXN 30005 9 #define INF 0x3f3f3f3f 10 using namespace std; 11 12 map<char,int> m; 13 vector<int> G[MAXN],c[MAXN]; 14 int M,dis[MAXN],vis[MAXN]; 15 16 struct cc{int num,d;}; 17 cc make(int num,int d){cc a;a.num=num;a.d=d;return a;} 18 struct cmp{bool operator()(cc a,cc b){return a.d>b.d;}}; 19 int trans(char a){return m[a];} 20 21 void init_(){ 22 int j=1; for(char i='a';i<='z';i++,j++){m[i]=j;} 23 j=30; for(char i='A';i<='Z';i++,j++){m[i]=j;} 24 scanf("%d",&M); 25 26 for(int i=1;i<=M;i++){ 27 char a,b;int w;//格式化輸入？？？ 28 cin>>a>>b>>w; 29 G[trans(a)].push_back(trans(b));c[trans(a)].push_back(w); 30 G[trans(b)].push_back(trans(a));c[trans(b)].push_back(w); 31 } 32 } 33 34 35 void Dijkstra(){ 36 priority_queue<cc,vector<cc>,cmp> q; 37 memset(dis,0x3f,sizeof(dis)); 38 int s=trans('Z'); 39 dis[s]=0;q.push(make(s,0)); 40 while(!q.empty()){ 41 int x=q.top().num;q.pop(); 42 if(vis[x]) continue;vis[x]=1; 43 // puts("@"); 44 for(int i=0;i<G[x].size();i++){ 45 int to=G[x][i]; 46 if(dis[x]+c[x][i]<dis[to]){ 47 dis[to]=dis[x]+c[x][i]; 48 q.push(make(to,dis[to])); 49 } 50 } 51 } 52 } 53 54 void work(){ 55 Dijkstra(); 56 char ans_num;int ans_step=INF; 57 58 for(char i='A';i<'Z';i++) 59 if(dis[trans(i)]<ans_step) 60 ans_num=i,ans_step=dis[trans(i)]; 61 62 cout<<ans_num<<" "<<ans_step<<endl; 63 } 64 65 int main(){ 66 // freopen("01.in","r",stdin);//freopen("01.out","w",stdout); 67 68 init_(); 69 work(); 70 71 fclose(stdin);fclose(stdout);return 0; 72 }回顧了一下 最短路+map 的神奇組合
)
.doc...)
