大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
人活着系列之开会
Time Limit: 1000MS Memory limit: 65536K
题目描写叙述
人活着假设是为了事业。从打工的到老板的,个个都在拼搏,奋斗了多年最终有了非凡成就。有了一笔丰富的钱財。反过来说。人若赚取了全世界又有什么益处呢?生不带来。死了你还能带去吗?金钱能买保险,但不能买生命,金钱能买药品,但不能买健康,人生在世,还是虚空呀!
在苍茫的大海上。有非常多的小岛。每一个人都在自己的小岛上。
又到了开会的时候了,鹏哥通过飞信告知了每一个人,然后大家就開始往鹏哥所在的主岛走,问谁先到达主岛。
有几点注意事项:
-
主岛一定除了鹏哥之外没有不论什么人。
-
并不是全部的小岛上都有人,有的小岛为空。
-
例子保证一定有人会先到达主岛。
-
小岛上最多仅仅有一个人。
-
每一个人往主岛走的速度同样
-
每一个小岛都有一条或多条路与别的小岛相连,可能和自己有一条路相连
-
至少有一个小岛和主岛相连。保证全部的人都能够到达主岛
-
为了节约时间,每一个人都走最短的路径
-
两个岛之间或许不仅仅有一条路相连。
-
每一个小岛都被标记为字母,大写字母代表这个小岛有人,小写字母代表这个小岛没有人。Z代表鹏哥所在主岛的位置
-
A和a表示两个不同的牧场。A a 8代表的是A岛到a岛的距离是8 ,A岛上是有人的,a岛上是没有人的。
输入
第一行 :N ,代表着大海上一共同拥有N条连接小岛的路,(1<= N<=10000)
接下来N行,每一行有两个字母和一个整数len,代表着两个岛的标记是否存在人。以及这两个岛之间的距离。(1<=len<=1000)
输出
最先到达主岛的那个人所在的岛的字母以及他走过的路径长度。
演示样例输入
6 A e 6 e Z 8 B c 3 c d 2 D A 12 d Z 3
演示样例输出
B 8
题目不难,仅仅需将字母转化为矩阵的坐标。大写和小写字母一共52个,弗洛伊德肯定过
11条注意。非常重要
#include <iostream> #include <cstdio> #include <cstring> #include <math.h> #include <cstdlib> #include <algorithm> const int INF = 1e6; using namespace std; int dis[110][110],sum; void init() { for(int i = 1;i <= 52;i ++) { for(int j = 1;j <= 52;j++) { if(i==j) dis[i][j] = 0; else dis[i][j] = INF; } } } int GET(char a) { if(a >= 'A'&&a <= 'Z') return a-'A'+1; else return a-'a'+27; } void Flyed() { sum = INF; for(int k = 1;k<53;k++) { for(int i = 1;i<53;i++) { for(int j = 1;j<53;j++) { if(dis[i][j] > dis[i][k]+dis[k][j]) dis[i][j] = dis[i][k]+dis[k][j]; } } } } int main() { int n,c; char a[5],b[5]; scanf("%d",&n); getchar(); init(); for(int i = 1;i <= n;i ++) { scanf("%s%s%d",a,b,&c); int x = GET(a[0]); int y = GET(b[0]); if(dis[x][y] > c) { dis[x][y] = dis[y][x] = c; } } Flyed(); int st; for(int i = 1;i<26;i++) { if(sum > dis[i][26]) { sum = dis[i][26]; st = i; } } st--; printf("%c %d\n",st+'A',sum); return 0; }
版权声明:本文博主原创文章,博客,未经同意不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116750.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...