题目描述:输入的第一行有三个数,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 ;
}

最新文章

  1. 一位同事对 Rafy 框架的一些建议及我的回复
  2. SQL--create Table
  3. .NET MEF入门级例子
  4. Java Hour 25 Packages
  5. Spring Boot 学习笔记 - 认识Spring Boot框架
  6. DevExpress navBarControl 和 xtraTabbedMdiManager实现浏览器标签页效果
  7. windows phone 生产含logo的二维码
  8. Scala学习文档-各种使用模式的情况
  9. Use Excel to write insert SqlScript
  10. attachEvent和addEventListener详解
  11. ASP.NET MVC+EF框架+EasyUI实现权限管理系列(1)-框架搭建
  12. C++开发象棋一 绘制棋盘
  13. windows 堆管理
  14. XML使用练习
  15. Qt中实现启动画面
  16. 多线程之Executors基本使用
  17. 不能靠眼睛之 KEIL 中失效代码灰暗特性
  18. (0-1)CSS 标签语法的属性
  19. PLSQL Developer windows 64位连接数据库的问题
  20. C++ 类之间的互相调用

热门文章

  1. Gartner研究副总裁:人工智能的五点傲慢与偏见
  2. Sprint 1 Review &amp; Daily Scrum - 11/18
  3. [福大软工] Z班 个人项目自动测试结果
  4. 基于 Java Web 的毕业设计选题管理平台--测试报告与用户手册
  5. XCODE 6.1.1 配置GLFW
  6. 分析code
  7. dispatch_block_t
  8. C语言入门:03.关键字、标识符、注释
  9. 【大数据】SparkCore学习笔记
  10. SSH协议详解