hdu-2112-HDU Today(dijkstra + map)

简介: hdu-2112-HDU Today(dijkstra + map)


HDU Today

Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 19610    Accepted Submission(s): 4609


Problem Description

经过锦囊相助,海东集团终于度过了危机,从此,HDU的发展就一直顺风顺水,到了2050年,集团已经相当规模了,据说进入了钱江肉丝经济开发区500强。这时候,XHD夫妇也退居了二线,并在风景秀美的诸暨市浬浦镇陶姚村买了个房子,开始安度晚年了。

这样住了一段时间,徐总对当地的交通还是不太了解。有时很郁闷,想去一个地方又不知道应该乘什么公交车,在什么地方转车,在什么地方下车(其实徐总自己有车,却一定要与民同乐,这就是徐总的性格)。

徐总经常会问蹩脚的英文问路:“Can you help me?”。看着他那迷茫而又无助的眼神,热心的你能帮帮他吗?

请帮助他用最短的时间到达目的地(假设每一路公交车都只在起点站和终点站停,而且随时都会开)。

 


Input

输入数据有多组,每组的第一行是公交车的总数N(0<=N<=10000);

第二行有徐总的所在地start,他的目的地end;

接着有n行,每行有站名s,站名e,以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。

note:一组数据中地名数不会超过150个。

如果N==-1,表示输入结束。

 


Output

如果徐总能到达目的地,输出最短的时间;否则,输出“-1”。

 


Sample Input

      6 xiasha westlake xiasha station 60 xiasha ShoppingCenterofHangZhou 30 station westlake 20 ShoppingCenterofHangZhou supermarket 10 xiasha supermarket 50 supermarket westlake 10 -1      

 


Sample Output

      50 Hint: The best route is: xiasha->ShoppingCenterofHangZhou->supermarket->westlake 虽然偶尔会迷路,但是因为有了你的帮助 **和**从此还是过上了幸福的生活。 ――全剧终――      

 


Author

lgx

 


Source

ACM程序设计_期末考试(时间已定!!)

 


Recommend

lcy   |   We have carefully selected several similar problems for you:   2544  1217  1142  1385  1548

 


题目分析:

就是简单的dijkstra  难点在于车站没给编号只给了名字   所以应该给车站编号怎么编呢?

显然的就是 map       map对于字符串的处理是很有用的        map详解   map  set  list  真心很好用  不过我感觉map用处更多


#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<string>
#define INF 0x3f3f3f3f
#define M  200
using namespace std;
int cost[M][M],dis[M],mark[M];
int n,cnt;
char str1[31],str2[31];
void dijkstra(int s)// 这一部分就是模板没什么好说的
{
  memset(mark,0,sizeof(mark));
  memset(dis,INF,sizeof(dis));
  dis[s]=0;
  while(1)
  {
    int v=-1;
    for(int i=1;i<cnt;i++)
       if(!mark[i]&&(v==-1||dis[i]<dis[v]))
          v=i;
    if(v==-1)  break;
    mark[v]=1;
    for(int i=0;i<cnt;i++)
         dis[i]=min(dis[i],dis[v]+cost[v][i]);
  }
}
int main()
{
  map<string,int> st;// 定义map
  while(~scanf("%d",&n)&&n!=-1)
  {
          st.clear();// 每次使用前清零
    memset(cost,INF,sizeof(cost));
    scanf("%s%s",str1,str2);
    st[str1]=1;//  起点站标为 1
    st[str2]=2;//  终点标为  2
    cnt=3;  
    int flag=0;
    if(strcmp(str1,str2)==0)  flag=1;//  如果终点起点相同  标记为 1
    while(n--)
    {
      int time;
      scanf("%s%s%d",str1,str2,&time);
      if(!st[str1])  st[str1]=cnt++;// 如果这个车站没出现过那么就要加一意思是出现新站点了
      if(!st[str2])  st[str2]=cnt++;// 同上
      if(cost[st[str1]][st[str2]]>time)//  重复出现的去最小时间
           cost[st[str1]][st[str2]]=cost[st[str2]][st[str1]]=time;
    }
    dijkstra(1);
    //printf("%d\n",cnt);
    if(flag)  printf("0\n");
    else
      printf("%d\n",dis[2]==INF?-1:dis[2]);
    
  }
  return 0;
}



目录
相关文章
|
数据采集 监控 JavaScript
网站流量日志分析— —数据采集—使用 web 服务器自带日志记录采集|学习笔记
快速学习网站流量日志分析——数据采集—使用 web 服务器自带日志记录采集
805 0
网站流量日志分析— —数据采集—使用 web 服务器自带日志记录采集|学习笔记
|
9月前
|
Java
Java 面向对象编程的三大法宝:封装、继承与多态
本文介绍了Java面向对象编程中的三大核心概念:封装、继承和多态。
464 15
|
12月前
|
存储 Python
CSV文件
【10月更文挑战第18天】CSV文件
748 2
|
8月前
|
机器学习/深度学习 算法 PyTorch
从零开始深度学习:全连接层、损失函数与梯度下降的详尽指南
在深度学习的领域,全连接层、损失函数与梯度下降是三块重要的基石。如果你正在踏上深度学习的旅程,理解它们是迈向成功的第一步。这篇文章将从概念到代码、从基础到进阶,详细剖析这三个主题,帮助你从小白成长为能够解决实际问题的开发者。
|
10月前
|
人工智能 编解码 机器人
NVILA:英伟达开源视觉语言大模型,高效处理高分辨率图像和长视频
NVILA是英伟达推出的视觉语言大模型,旨在高效处理高分辨率图像和长视频,同时保持高准确性。该模型通过“扩展-压缩”策略和多种优化技术,在多个领域如机器人导航和医疗成像中展现出广泛的应用潜力。
342 13
NVILA:英伟达开源视觉语言大模型,高效处理高分辨率图像和长视频
|
9月前
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
205 10
|
12月前
|
安全 数据管理 定位技术
CDGA|自然资源数据治理五部曲,实现数据融合关联、共享可用
在自然资源行业,数据治理是自然资源信息化的工作基础,是推进自然资源治理体系和治理能力现代化进程的必经之路。
|
SQL 存储 关系型数据库
PolarDB-X CDC之"兼容MySQL,高于MySQL"
本文主要介绍一下PolarDB-X在CDC能力上那些高阶能力。
|
XML Java 数据格式
【Lua基础 第2章】lua遍历table的方式、运算符、math库、字符串操作方法
lua遍历table的方式、运算符、math库、字符串操作方法
974 0
【Lua基础 第2章】lua遍历table的方式、运算符、math库、字符串操作方法
|
安全 前端开发 Java
Scala与Java:综合比较
Scala与Java:综合比较
309 0