HDU 2066 一个人的旅行 最短路问题
2024-10-13 10:54:29
题目描述:输入的第一行有三个数,T,S,D,T表示一共有多少条线路,S表示起点的个数,D表示终点的个数,接下来就是输入T条路的信息了,要你判断从多个起点中任意一个到多个终点中的任意的一个的最短距离是多少。
解题报告:这题与其他的题目最大的不同就是这题的起点和终点都有多个,不然就可以用迪杰斯特拉来解了,但是虽然这题有多个起点和多个终点,我们可不可以把它转化成用迪杰斯特拉解决的问题的类型呢,即转化成单个起点的问题呢? 答案是可以的,我们完全可以假设一个虚拟的起点和一个虚拟的终点,即将原来的N个点的图再加两个,变成N+2 个点图,一个起点一个终点,我们可以令实际上的起点到虚拟的起点的距离是一个定值,同理,令所有的终点到虚拟的终点的距离也是一个定值,这样就可以轻松的转化成用单源的最短路问题了,用迪杰斯特拉即可解出。
#include<cstdio>
#include<cstring>
#include<iostream>
const int MAX = 0xfffff,SIZE = +;
int T1,S,D,map[SIZE][SIZE],f,T[SIZE],visit[SIZE];
int main() {
int a,b,len,x,y;
while(scanf("%d%d%d",&T1,&S,&D)!=EOF) {
memset(map,0x3f,sizeof(map));
memset(T,0x3f,sizeof(T));
printf("%d\n",T[]);
f = ;
for(int i = ;i<=T1;++i) {
scanf("%d%d%d",&a,&b,&len);
f = std::max(a,f); //找到编号最大的点以确定范围
f = std::max(b,f);
map[a][b] = map[b][a] = std::min(len,map[a][b]);
//如果有多条路径,取权值最小的
}
for(int i = ;i<=S;++i) { //增加虚拟起点到草儿家附近的城市的距离
scanf("%d",&a);
map[][a] = map[a][] = ;
}
f++; //增加一个虚拟的终点
for(int i = ;i<=D;++i) { //增加虚拟起点到草儿想去的城市的距离
scanf("%d",&a);
map[f][a] = map[a][f] = ;
}
int s = ;
T[s] = ;
memset(visit,,sizeof(visit));
while() {
if(s == f)
break;
for(int i = ;i<=f;++i)
if(!visit[i]&&(T[i]>(T[s]+map[s][i])))
T[i] = T[s]+map[s][i];
visit[s] = ;
s = f+;
bool flag = ;
for(int i = ;i<=f;++i)
if(!visit[i]&&T[i]<T[s]) {
s = i;
flag = ;
}
if(flag)
break;
}
printf("%d\n",T[f]-);
}
return ;
}
最新文章
- 一位同事对 Rafy 框架的一些建议及我的回复
- SQL--create Table
- .NET MEF入门级例子
- Java Hour 25 Packages
- Spring Boot 学习笔记 - 认识Spring Boot框架
- DevExpress navBarControl 和 xtraTabbedMdiManager实现浏览器标签页效果
- windows phone 生产含logo的二维码
- Scala学习文档-各种使用模式的情况
- Use Excel to write insert SqlScript
- attachEvent和addEventListener详解
- ASP.NET MVC+EF框架+EasyUI实现权限管理系列(1)-框架搭建
- C++开发象棋一 绘制棋盘
- windows 堆管理
- XML使用练习
- Qt中实现启动画面
- 多线程之Executors基本使用
- 不能靠眼睛之 KEIL 中失效代码灰暗特性
- (0-1)CSS 标签语法的属性
- PLSQL Developer windows 64位连接数据库的问题
- C++ 类之间的互相调用