大专网站建设资料,哈尔滨市做网站优化,google chrome官网,济南做网站互联网公司排名题目描述 现在是晚餐时间,而母牛们在外面分散的牧场中。 农民约翰按响了电铃,所以她们开始向谷仓走去。 你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只最快的母牛)。 在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛。…题目描述 现在是晚餐时间,而母牛们在外面分散的牧场中。 农民约翰按响了电铃,所以她们开始向谷仓走去。 你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只最快的母牛)。 在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛。 每个牧场由一条条道路和一个或多个牧场连接(可能包括自己)。 有时两个牧场(可能是字母相同的)之间会有超过一条道路相连。 至少有一个牧场和谷仓之间有道路连接。 因此,所有的母牛最后都能到达谷仓,并且母牛总是走最短的路径。 当然,母牛能向着任意一方向前进,并且她们以相同的速度前进。 牧场被标记为a..z和A..Y,在用大写字母表示的牧场中有一只母牛,小写字母中则没有。 谷仓的标记是Z,注意没有母牛在谷仓中。 注意m和M不是同一个牧场 否则错误 上面的意思是说输入数据中可能会同时存在M,m郁闷ing)(PS:表郁闷…告诉我set of咋用就不郁闷了…)比如 M a a m m z 输入输出格式 输入格式 第 1 行: 整数 P(1 P10000),表示连接牧场(谷仓)的道路的数目。 第 2 ..P1行: 用空格分开的两个字母和一个整数: 被道路连接牧场的标记和道路的长度(1长度1000)。 输出格式 单独的一行包含二个项目: 最先到达谷仓的母牛所在的牧场的标记,和这只母牛走过的路径的长度。 输入输出样例 输入样例#15
A d 6
B d 3
C e 9
d Z 8
e Z 3 输出样例#1B 11说明 翻译来自NOCOW USACO 2.4 代码 1 #includealgorithm2 #includeiostream3 #includecstring4 #includecstdio5 #includevector6 #includequeue7 #includemap8 #define MAXN 300059 #define INF 0x3f3f3f3f
10 using namespace std;
11
12 mapchar,int m;
13 vectorint 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.numnum;a.dd;return a;}
18 struct cmp{bool operator()(cc a,cc b){return a.db.d;}};
19 int trans(char a){return m[a];}
20
21 void init_(){
22 int j1; for(char ia;iz;i,j){m[i]j;}
23 j30; for(char iA;iZ;i,j){m[i]j;}
24 scanf(%d,M);
25
26 for(int i1;iM;i){
27 char a,b;int w;//格式化输入
28 cinabw;
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_queuecc,vectorcc,cmp q;
37 memset(dis,0x3f,sizeof(dis));
38 int strans(Z);
39 dis[s]0;q.push(make(s,0));
40 while(!q.empty()){
41 int xq.top().num;q.pop();
42 if(vis[x]) continue;vis[x]1;
43 // puts();
44 for(int i0;iG[x].size();i){
45 int toG[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_stepINF;
57
58 for(char iA;iZ;i)
59 if(dis[trans(i)]ans_step)
60 ans_numi,ans_stepdis[trans(i)];
61
62 coutans_num ans_stependl;
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 的神奇组合 转载于:https://www.cnblogs.com/radiumlrb/p/6048897.html
