hdu 2112 HDU Today 解题报告
2024-09-08 15:45:37
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2112
题目意思:又是求最短路的,不过结合埋字符串来考查。
受之前1004 Let the Balloon Rise 学到用map 的解法做之后,有点蠢蠢欲动,当时见到要用字典树做有点吓坏了(之前看过下,非一般难理解,所以暂时放下了)。于是,死就死吧,硬住头皮用map做,反反复复修改终于过了。
首先是memory limit exceeded,因为无读清题目意思,直接开10000 * 10000的数组= =。细心留意这句话:note:一组数据中地名数不会超过150个。表示150 * 150 的数组即可!!
接着就一直wa了,原因:无把map 清空!注意注意啊,用 STL 的时候要特别注意。还有一个就是起点与终点重合应该输出0,不可达输出-1,否则输出结果。
还有一个小细节,代码中的 l 不要贪方便写在 for (int i = 0; i < n; i++) 循环里面,因为出了这个循环之后,l 对其他部分是不可见的,默认变为0。而我们是需要 l 的值,因为它记录了每个站名依次对应的编号。
呕心沥血版,新鲜出炉啊~~~~
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string> // 这个头文件不能缺,否则会CE
#include <map>
using namespace std; const int INF = 0xffffff;
const int maxn = + ;
int dist[maxn], grid[maxn][maxn], vis[maxn];
int n, l, cost, flag;
map<string, int> zhan; void Init()
{
memset(grid, , sizeof(grid)); // 这个也是关键,因为下面的if (!grid[i][j]) 要用到,表示无边直接相连的点的距离设为INF
zhan.clear(); // 关键关键!!!!
flag = , l = ;
string tmp1, tmp2;
cin >> tmp1 >> tmp2;
if (tmp1 == tmp2)
flag = ;
zhan[tmp1] = ; // 起点为1,终点为2
zhan[tmp2] = ;
for (int i = ; i < n; i++) // 为每个站名编号
{
cin >> tmp1 >> tmp2 >> cost;
if (zhan[tmp1] == )
{
zhan[tmp1] = l;
l++;
}
if (zhan[tmp2] == )
{
zhan[tmp2] = l;
l++;
}
grid[zhan[tmp1]][zhan[tmp2]] = grid[zhan[tmp2]][zhan[tmp1]] = cost;
}
for (int i = ; i < l; i++)
{
for (int j = ; j < l; j++)
{
if (!grid[i][j])
grid[i][j] = grid[j][i] = INF;
}
}
dist[] = ; // 离自己的距离为0
for (int i = ; i < l; i++) // 求出其他站离它的距离是多少
dist[i] = grid[][i];
} void Dijkstra()
{
memset(vis, , sizeof(vis));
for (int i = ; i < l; i++)
{
int u;
int maxx = INF;
for (int j = ; j < l; j++)
{
if (!vis[j] && dist[j] < maxx)
maxx = dist[u = j];
}
vis[u] = ;
for (int j = ; j < l; j++)
{
if (dist[j] > dist[u] + grid[u][j])
dist[j] = dist[u] + grid[u][j];
}
}
if (flag) // 代表起点与终点重合!
printf("0\n");
else
printf("%d\n", dist[] == INF ? - : dist[]);
} int main()
{
while (scanf("%d", &n) && n != -) // n: 城市, m:道路
{
Init();
Dijkstra();
}
return ;
}
最新文章
- 基于DDD的.NET开发框架 - ABP领域服务
- Beta--项目冲刺第七天
- JDBC Driver
- 跨站点端口攻击 – XSPA(SSPA)
- hdu 4039 暴力
- UML统一建模语言
- QRadionButton 圆点样式
- DG创建和提取虚拟机文件
- truncate 和 delete 差异
- Linux命令之文本处理(二)
- $(";li";)是对象类型不是数组类型
- verilog实现红黄蓝三秒灯
- go 学习资源和GitHub库
- Python_模块介绍
- centos7学习笔记-安装后的一些配置
- 【读书笔记】iOS-正则表达式
- 简单Demo 使用Code Fisrt步骤
- JSP JSTL知识结构图
- php如何使用rabbitmq实现发布消息和消费消息(一对多)(tp框架)(第二篇)
- LNMP zabbix安装
热门文章
- 使用 ftrace 调试 Linux 内核,第 2 部分
- Laravel 控制器的response
- android apk程序升级
- Java运算基础
- VirtualBox虚拟机出现被召者 RC: E_NOINTERFACE (0x80004002)
- MySQL主从架构配置
- inux IO 内核参数调优 之 参数调节和场景分析
- WIP - 离散任务点击组件-错误:LOCATOR.CONTROL 的变元无效:ORG_LOCATOR_CONTROL=''
- linxu下的shell脚本加密,shell生成二机制可执行文件
- Matlab多项式拟合測试