郑州app开发公司排名,网站seo 文章转载 修改标题,做h5的图片网站,北京科技网站建设公司Bessie Come Home回家
题目大意:
有n条路连接着一些牧场#xff0c;每个牧场由‘a-z’#xff08;没羊#xff09;和‘A-Y’#xff08;有一头羊#xff09;#xff0c;问哪个有羊的牧场离‘Z’最近
INPUT FORMAT
第 1 行: 整数 P(1 P10000),表示连接牧场(谷…Bessie Come Home回家
题目大意:
有n条路连接着一些牧场每个牧场由‘a-z’没羊和‘A-Y’有一头羊问哪个有羊的牧场离‘Z’最近
INPUT FORMAT
第 1 行: 整数 P(1 P10000),表示连接牧场(谷仓)的道路的数目。
第 2 …P1行: 用空格分开的两个字母和一个整数:
被道路连接牧场的标记和道路的长度(1长度1000)。
SAMPLE INPUT
5
A d 6
B d 3
C e 9
d Z 8
e Z 3
OUTPUT FORMAT
单独的一行包含二个项目:
最先到达谷仓的母牛所在的牧场的标记,和这只母牛走过的路径的长度。
SAMPLE OUTPUT
B 11
解题思路
首先字符先进行一些操作变成数字然后用SPFA求出最短路然后从有羊的牧场中选离‘Z’最近的牧场然后再转换成字符再输出还要输出他的距离
#includecstdio
#includeiostream
#includecstring
#includequeue
using namespace std;
int h,now,w,g,ans,n,x,y,c[60],b[60],head[60],p[60];
char st,st1;
struct rec
{int to,l,next;
}f[20005];
int main()
{scanf(%d,n);for (int i1;in;i){cinstst1;if (stastz) xst-a1;//小写else {xst-A27;//大写c[x]1;//记录}if (st1ast1z) yst1-a1;else {yst1-A27;c[y]1;}scanf(%d,g);f[w].toy;//去向f[w].lg;//距离f[w].nexthead[x];//下一条线head[x]w;//x点的第一条线f[w].tox;f[w].lg;f[w].nexthead[y];head[y]w;}memset(b,127/3,sizeof(b));//预处理queueintd; d.push(52);//入队p[52]1;//记录b[52]0;//预处理while(!d.empty())//结束没{nowd.front();//去出头元素d.pop();//出队for (int ihead[now];i;if[i].next)//连接此点的每一条线if (b[now]f[i].lb[f[i].to])//判断是否更优{b[f[i].to]b[now]f[i].l;//代替if(!p[f[i].to])//判断是否在队列内{d.push(f[i].to);//入队p[f[i].to]1;//记录}}p[now]0;//清空}ans2147483647;//预处理for(int i1;i52;i)//每一个牧场if (c[i]b[i]ans)//有没有羊是否更优{ansb[i];//代替hi;//记录}if (h26) putchar(ah-1);//弄回字符else putchar(Ah-27);printf( %d,ans);//输出
}
