14.回家(最短路径)

回家(最短路径)

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 白银 Silver

题解

查看运行结果

题目描述 Description

现在是晚餐时间,而母牛们在外面分散的牧场中。农民约翰按响了电铃,所以她们开始向谷仓走去。你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只最快的母牛)。 在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛。 每个牧场由一条条道路和一个或多个牧场连接(可能包括自己)。 有时,两个牧场(可能是字母相同的)之间会有超过一条道路相连。 至少有一个牧场和谷仓之间有道路连接。 因此,所有的母牛最后都能到达谷仓,并且母牛总是走最短的路径。 当然,母牛能向着任意一方向前进,并且她们以相同的速度前进。 牧场被标记为‘a‘..‘z‘和‘A‘..‘Y‘,在用大写字母表示的牧场中有一只母牛,小写字母中则没有。 谷仓的标记是‘Z‘,注意没有母牛在谷仓中。

注意‘m‘和‘M‘不是同一个牧场否则错误上面的意思是说:输入数据中可能会同时存在M,m(郁闷ing),比如

M a a m m z

输入描述 Input Description

第1 行: 整数 P(1<= P<=10000),表示连接牧场(谷仓)的道路的数目。

第2 ..P+1行:  用空格分开的两个字母和一个整数:

被道路连接牧场的标记和道路的长度(1<=长度<=1000)。

输出描述 Output Description

单独的一行包含二个项目:最先到达谷仓的母牛所在的牧场的标记,和这只母牛走过的路径的长度。

样例输入 Sample Input

5

A d 6

B d 3

C e 9

d Z 8

e Z 3

样例输出 Sample Output

B 11

代码:

#include

using namespace std;

#include

#include

#include

struct MC{

int data,dist;

};

MC mc[53];

int p;

int dis1[53][53];

int visit[53]={0};

int cmp(const MC &a,const MC &b)

{

return a.dist

}

void input()

{

for(int i=1;i<=52;++i)

mc[i].data=i;//将每个点的编号记下来

scanf("%d",&p);

char a1,b1;

int a,b;

for(int i=1;i<=52;++i)

for(int j=1;j<=52;++j)

dis1[i][j]=99999;//距离一开始都设为最大值

for(int i=1;i<=52;++i)

mc[i].dist=99999;

mc[26].dist=0;//A--Z用1---26表示,a---z用27---52表示

int t;

for(int i=1;i<=p;++i)

{

scanf("%c%c",&a1,&b1);

scanf("%c%c%c",&a1,&b1,&b1);

if(a1>=‘A‘&&a1<=‘Z‘)

a=a1-‘A‘+1;

if(b1>=‘A‘&&b1<=‘Z‘)

b=b1-‘A‘+1;

if(a1>=‘a‘&&a1<=‘z‘)

a=a1-‘a‘+27;

if(b1>=‘a‘&&b1<=‘z‘)

b=b1-‘a‘+27;

scanf("%d",&t);

if(t处理两点之间有多条路径,取最短的一条

dis1[b][a]=dis1[a][b]=t;

if(a==b)//处理自己到自己的路径

dis1[a][b]=dis1[b][a]=0;

if(a==26)//记录到Z终点的距离

{

mc[b].dist=dis1[a][b];

}

if(b==26)

{

mc[a].dist=dis1[b][a];

}

}

}

void djkstra()

{

visit[26]=1;

for(int i=1;i<=p;++i)

{

int min=99999,k=0;

for(int j=1;j<=52;++j)

{

if(visit[j]==0&&mc[j].dist

{

min=mc[j].dist;

k=j;

}

}

if(k==0) break;

visit[k]=1;

for(int l=1;l<=52;++l)

{

if(mc[l].dist>mc[k].dist+dis1[k][l])

mc[l].dist=mc[k].dist+dis1[k][l];

}

}

}

int main()

{

input();

djkstra();

sort(mc+1,mc+26+1,cmp);//把A--Z的最短距离求出来

char zf;

for(int i=1;i<=52;++i)

{

if(mc[i].data>=1&&mc[i].data<=25)//只有大写字符上有奶牛

{

zf=mc[i].data+‘A‘-1;

printf("%c %d",zf,mc[i].dist);

break;

}

}

return 0;

}

时间: 03-15

14.回家(最短路径)的相关文章

最短路径算法

最短路径-Dijkstra算法和Floyd算法 1.Dijkstra算法 1.1.定义概览Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等.注意该算法要求图中不存在负权边. 问题描述:在无向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由顶点

最短路径-Dijkstra算法与Floyd算法

一.最短路径 ①在非网图中,最短路径是指两顶点之间经历的边数最少的路径. AE:1    ADE:2   ADCE:3   ABCE:3 ②在网图中,最短路径是指两顶点之间经历的边上权值之和最短的路径. AE:100   ADE:90   ADCE:60   ABCE:70 ③单源点最短路径问题 问题描述:给定带权有向图G=(V, E)和源点v∈V,求从v到G中其余各顶点的最短路径. 应用实例--计算机网络传输的问题:怎样找到一种最经济的方式,从一台计算机向网上所有其它计算机发送一条消息. ④每

图的基础知识

1.概念 图: 是一种复杂的非线性数据结构.图的二元组定义:  图 G 由两个集合 V 和 E 组成,记为:  G=(V, E)  其中: V 是顶点的有穷非空集合,  E 是 V 中顶点偶对(称为边)的有穷集. 通常,也将图 G 的顶点集和边集分别记为 V(G) 和 E(G) . E(G) 可以是空集.若 E(G) 为空,则图 G 只有顶点而没有边. 有向图: 若图 G 中的每条边都是有方向的,则称 G 为有向图 (Digraph) .无向图: 若图 G 中的每条边都是没有方向的,则称 G 为

减肥日记

2020.1.14 回家第二天,减肥第二天. 12日晚上到家 熬夜了,因为火车坐13小时处在半梦半醒的神游状态实在是令人精神恍惚 不是累也不是不累的状态,混合着列车特有的气味,手上身上全是那种味道,所幸回到家中洗澡后味道散去. 13日,自己买了十块钱的菜,鸡胸肉一块,红苕两个,荷兰豆几两 自己第一次做鸡胸肉,饮食控制. 早晨吃了外婆做的面条,中午米饭吃的较少和藕炖排骨,晚上没有米饭,自制鸡胸肉腌制过后味道还不错,得力于小苏打和刀叉敲打. 原文地址:https://www.cnblogs.com/

codves——1079 回家

1079 回家 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 现在是晚餐时间,而母牛们在外面分散的牧场中. 农民约翰按响了电铃,所以她们开始向谷仓走去. 你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只最快的母牛). 在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛. 每个牧场由一条条道路和一个或多个牧场连接(可能包括自己). 有时,两个牧场(可能是字母相同的)之间会有

[Swust OJ 767]--将军回家(Dijkstra算法)

题目链接:http://acm.swust.edu.cn/problem/767/ Time limit(ms): 1000 Memory limit(kb): 65535 Description 在涪江河的两边共有n个城市,其中位于一边的城市属于1类城市,另外一边的属于2类城市,(特别的:城市1属于1类,城市2属于2类).现在知道一些道路的情况,比如知道城市1到城市5之间有一条长度为100的路.将军要从城市1回到城市2的家,他就开始设计回家的线路.回家时由于驾照的关系,只能越过一次涪江河.现在

[BZOJ 1576] 安全路径 最短路径树 路径压缩

题意 给定一张 n 个点 m 条边的图, 保证对于任意的点 i , 从点 1 到点 i 的最短路唯一. 对于任意的点 i , 询问: 将 1 到 i 的最短路中最后一条边删去之后, 从 1 到 i 的最短路 . n <= 100000, m <= 200000 . 分析 首先跑 Dijsktra , 构建出最短路径树. 接下来考虑每条非树边 E[p] = (u, v, d) 对答案的影响, 它能且仅能影响到点 u, v 之上, LCA(u, v) 之下的点的答案. (包括 u, v, 不包括

2017年8月14日套题记录 | 普及组

写在前面 今天登洛谷发现离Noip剩下88天了??(虽然看起有点久),然后觉得似乎水了一个暑假什么也没做(虽然学了点数据结构和一些奇奇Gaygay的东西),于是打开题库发现去年Long Happy的集训套题我似乎没有提交过,那就一天一套题,顺便码个题解+心得(雾? T2.传作业 题目描述 某十三同学一日上学迟到,此时已经开始上早自习了,所以他只好请同学帮忙把作业传到组长那里.由于刚开学不久,某十三同学还没来得及认识所有同学,所以传作业时只好找熟悉的同学.已知某十三与组长之间有N个他熟悉的同学,并

蓝桥杯 最短路径问题

试题描述:最短路径问题.定义一个二维数组:int maze[][] = {    {0, 1, 0, 0, 0},    {0, 1, 0, 1, 0},    {0, 0, 0, 0, 0},    {0, 1, 1, 1, 0},    {0, 0, 0, 1, 0}};它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线.输出的效果是(0, 0)(1, 0)(2, 0)(2, 1)(2, 2)(2, 3)(2, 4)(