题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2112
HDU Today
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14527 Accepted Submission(s): 3412
这样住了一段时间。徐总对当地的交通还是不太了解。
有时非常郁闷,想去一个地方又不知道应该乘什么公交车。在什么地方转车,在什么地方下车(事实上徐总自己有车,却一定要与民同乐,这就是徐总的性格)。
徐总常常会问蹩脚的英文问路:“Can you help me?”。看着他那迷茫而又无助的眼神,热心的你能帮帮他吗?
请帮助他用最短的时间到达目的地(如果每一路公交车都仅仅在起点站和终点站停。并且随时都会开)。
第二行有徐总的所在地start,他的目的地end;
接着有n行,每行有站名s,站名e,以及从s到e的时间整数t(0<t<100)(每一个地名是一个长度不超过30的字符串)。
note:一组数据中地名数不会超过150个。
假设N==-1。表示输入结束。
6
xiasha westlake
xiasha station 60
xiasha ShoppingCenterofHangZhou 30
station westlake 20
ShoppingCenterofHangZhou supermarket 10
xiasha supermarket 50
supermarket westlake 10
-1
50 Hint:
The best route is:
xiasha->ShoppingCenterofHangZhou->supermarket->westlake 尽管偶尔会迷路,可是由于有了你的帮助
**和**从此还是过上了幸福的生活。 ――全剧终――
pid=1385" target="_blank">1385
1690pid=2722" target="_blank">2722
#pragma warning (disable:4786)
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#include <climits>
#include <ctype.h>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define PI acos(-1.0)
#define INF 0x3fffffff
//typedef long long LL;
//typedef __int64 LL;
#define MAXN 10017
#define M 32
int mat[MAXN][MAXN];
int n;
#define MAX 150
map<string,int>m;
void init()
{
for(int i = 0; i <= MAX; i++)
{
for(int j = 0; j <= MAX; j++)
{
if(i == j)
mat[i][j] = 0;
else
mat[i][j] = INF;
}
}
m.clear();
} int dijkstra (int s,int f)
{
//s为起点, f:为终点
int dis[MAXN];//记录到随意点的最短距离
int mark[MAXN];//记录被选中的结点
int i,j,k = 0;
for(i = 0; i <= MAX; i++)
{
mark[i] = 0;//初始化全部结点,每一个结点都没有被选中
dis[i] = INF;
}
mark[s] = 1;//start结点被选中
dis[s] = 0;//将start结点的的距离设置为0
int min ;//设置最短的距离。
for(i = 1; i <= MAX; i++)
{
k = 1;
min = INF;
for(j = 1; j <= MAX; j++)
{
if(mark[j] == 0 && dis[j] < min)//未被选中的结点中,距离最短的被选中
{
min = dis[j] ;
k = j;
}
}
mark[k] = 1;//标记为被选中
for(j = 1; j <= MAX; j++)
{
if( mark[j] == 0 && (dis[j] > (dis[k] + mat[k][j])))//改动剩余结点的最短距离
{
dis[j] = dis[k] + mat[k][j];
}
}
}
return dis[f];
} int main()
{
int i;
char s[M], e[M], a[M], b[M];
int v;
while(~scanf("%d",&n))
{
init();
if(n == -1)
break;
scanf("%s%s",s,e);
m[s] = 1;
if(!m[e])
m[e] = 2;
int c = 3;
for(i = 0; i < n; i++)
{
scanf("%s%s%d",a,b,&v);
if(!m[a])
m[a] = c++;
if(!m[b])
m[b] = c++;
if(v < mat[m[a]][m[b]])
{
mat[m[a]][m[b]] = v;
mat[m[b]][m[a]] = v;
}
}
int ans = dijkstra(m[s],m[e]);
if(ans == INF)
printf("-1\n");
else
printf("%d\n",ans);
}
return 0;
}
HDU 2112 HDU Today(Dijkstra)的更多相关文章
-
HDU 2544 最短路(Dijkstra)
https://vjudge.net/problem/HDU-2544 题意: 输入包括多组数据.每组数据第一行是两个整数N.M(N<=100,M<=10000),N表示成都的大街上有几个 ...
-
【HDU 6005】Pandaland(Dijkstra)
Problem Description Mr. Panda lives in Pandaland. There are many cities in Pandaland. Each city can ...
-
HDU 5938 Four Operations(四则运算)
p.MsoNormal { margin: 0pt; margin-bottom: .0001pt; text-align: justify; font-family: Calibri; font-s ...
-
HDU 5775 Bubble Sort(冒泡排序)
p.MsoNormal { margin: 0pt; margin-bottom: .0001pt; text-align: justify; font-family: Calibri; font-s ...
-
HDU 1711 Number Sequence(数列)
HDU 1711 Number Sequence(数列) Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Ja ...
-
HDU 1005 Number Sequence(数列)
HDU 1005 Number Sequence(数列) Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Jav ...
-
HDU 1176 免费馅饼 (动态规划)
HDU 1176 免费馅饼 (动态规划) Description 都说天上不会掉馅饼,但有一天gameboy正走在回家的小径上,忽然天上掉下大把大把的馅饼.说来gameboy的人品实在是太好了,这馅饼 ...
-
迪杰斯特拉(dijkstra)算法的简要理解和c语言实现(源码)
迪杰斯特拉(dijkstra)算法:求最短路径的算法,数据结构课程中学习的内容. 1 . 理解 算法思想::设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合 ...
-
最短路径之迪杰斯特拉(Dijkstra)算法
迪杰斯特拉(Dijkstra)算法主要是针对没有负值的有向图,求解其中的单一起点到其他顶点的最短路径算法.本文主要总结迪杰斯特拉(Dijkstra)算法的原理和算法流程,最后通过程序实现在一个带权值的 ...
-
理解最短路径——迪杰斯特拉(dijkstra)算法
原址地址:http://ibupu.link/?id=29 1. 迪杰斯特拉算法简介 迪杰斯特拉(dijkstra)算法是典型的用来解决最短路径的算法,也是很多教程中的范例,由荷兰计算机科 ...
随机推荐
-
ThinkPHP3.2.2 Widget扩展以及widget demo实例
Widget扩展一般用于页面组件的扩展. 先说明Widget被调用的方法,你只需要在你的模板文件中使用这样的语法:{:W("Demo/demo_widget_method",arr ...
-
HDP2.4安装(四):ambari安装
ambari是apache基金会的开源项目,它的优势在于巧妙溶合已有的开源软件,提供集群自动化安装.中心化管理.集群监控.报警等功能.据Hortonwork官方资料介绍,不同的HDP版本,对ambar ...
-
使用express搭建第一个Web应用【Node.js初学】
来源:http://jingyan.baidu.com/article/bad08e1ee501e009c8512106.html express是一个开源的node.js项目框架,初学者使用expr ...
-
ServiceBroker创建流程
首先为这个数据库开启Service Broker ALTER DATABASE [T_EIP_UnityStore] SET ENABLE_BROKER 创建MessageType CREATE ME ...
-
ref和out的使用与区别
out的使用 ————————————————————————————————————————————————— class Program { static void Main( ...
-
ASP.NET导出Excel(利用NPOI和EPPlus库,无需安装Office)
网上提供了很多Asp.net中操作Excel的方法,其中大部分是调用微软的Office组件,下面提供三个无须安装Office即可从Asp.net输出Excel的方法. 1 简单方法 //下面代码输出的 ...
-
dependent object 和root object
dependent object 是root object 下面的字节点.每个节点被访问,都要通过 root object 进入.
-
Matlab 将两个图像进行分离 已知其中一个图像
5.下图(a)是一幅两个灰度图像合成的图像,已知其中一幅图像如图(b)所示,试把另一幅图像提取出来,并显示. 运用减法做 %加载入要处理的图片 A=imread('a.png'); %将I变为[0,1 ...
-
Android人脸识别Demo竖屏YUV方向调整和图片保存
本博客包含三个常用方法,用于盛开Android版人脸识别Demo中竖屏使用时送入yuv数据,但一直无法识别的情况. 1.首先可以尝试顺时针旋转90°或270°,然后送入识别SDK. 2.旋转方向后依然 ...
-
Hadoop学习笔记02_MapReduce练习
搭建好环境之后 ,就来跑个简单的Mapreduce试试看吧.这个比第一课难多了,需要多多练习并熟练掌握. 需要编写py脚本以及shell脚本, 所以需要学习Python和Linux的Shell编程. ...