hdu 2066
2024-09-15 01:16:15
ps:我天...之前看了迪杰斯特拉..现在这题要用到floyd。。就是先建一个图,然后从列开始遍历，每列里遍历行,行又对应每列...
从A列开始遍历每行，比如遍历到B，这时候B->A知道是2，接着又遍历第一行，比如对应到C，就是B->A->C,如果B->A->C比B->C小，就把B->C更新,
感觉Floyd就是求每个点是否必须出现在某两个点之间，找出最短路径
另外这题比较坑的是，a,b之间可以有多条路......WA了几次...
代码:
#include "stdio.h"
#define MAX 1000000
int map[][];
int off[];
int begin[];
int want[];
int T,S,D,a,b,c,time;
void floyd(int t);
int main(){
int i,j,k,t,min1;
while(~scanf("%d%d%d",&T,&S,&D)){
t=;
for(i=;i<=;i++){
for(j=;j<=;j++){
map[i][j]=MAX;
}
}
for(i=;i<=T;i++){
scanf("%d%d%d",&a,&b,&c);
if(map[a][b]>c){
map[a][b]=c;
map[b][a]=c;
}
if(a>t){
t=a;
}
if(b>t){
t=b;
}
}
for(i=;i<=S;i++){
scanf("%d",&begin[i]);
}
for(i=;i<=D;i++){
scanf("%d",&want[i]);
}
floyd(t);
min1=MAX;
for(i=;i<=S;i++){
for(j=;j<=D;j++){
if(map[begin[i]][want[j]]<min1){
min1=map[begin[i]][want[j]];
}
}
}
printf("%d\n",min1);
}
return ;
}
void floyd(int t){
int i,j,k;
for(j=;j<=t;j++){
for(i=;i<=t;i++){
if(map[i][j]<MAX){
for(k=;k<=t;k++){
if(map[i][j]+map[j][k]<map[i][k]){
map[i][k]=map[i][j]+map[j][k];
}
}
}
}
}
}
#include "stdio.h"
#define MAX 1000000
int map[][];
int off[];
int begin[];
int want[];
int T,S,D,a,b,c,time;
void floyd(int t);
int main(){
int i,j,k,t,min1;
while(~scanf("%d%d%d",&T,&S,&D)){
t=;
for(i=;i<=;i++){
for(j=;j<=;j++){
map[i][j]=MAX;
}
}
for(i=;i<=T;i++){
scanf("%d%d%d",&a,&b,&c);
if(map[a][b]>c){
map[a][b]=c;
map[b][a]=c;
}
if(a>t){
t=a;
}
if(b>t){
t=b;
}
}
for(i=;i<=S;i++){
scanf("%d",&begin[i]);
}
for(i=;i<=D;i++){
scanf("%d",&want[i]);
}
floyd(t);
min1=MAX;
for(i=;i<=S;i++){
for(j=;j<=D;j++){
if(map[begin[i]][want[j]]<min1){
min1=map[begin[i]][want[j]];
}
}
}
printf("%d\n",min1);
}
return ;
}
void floyd(int t){
int i,j,k;
for(j=;j<=t;j++){
for(i=;i<=t;i++){
if(map[i][j]<MAX){
for(k=;k<=t;k++){
if(map[i][j]+map[j][k]<map[i][k]){
map[i][k]=map[i][j]+map[j][k];
}
}
}
}
}
}
最新文章
- Android 指纹认证
- 【VB6】使用VB6创建和访问Dom树【爬虫基础知识 】
- 统计在从1到n的正整数中1出现的次数
- 【POJ 2482】Stars in Your Window
- JSP题库
- MYSQL安装--小白教程
- ActionLink()与jquery更好地结合建造MVC网页：
- springMVC源码分析之拦截器
- 如何将根文件系统制作成yaffs格式，并设置从yaffs启动
- HDU 2586 LCA
- HTML5 <meta> 标签属性，所有meta用法都在这里了
- 在CENTOS6上安装MONGODB
- Ubuntu 修改 Apache2 用户组 方法
- 《Programming WPF》翻译 第7章 6.视频和3-D
- SQL子句执行顺序和Join的一点总结
- zzu--2014年11月16日月潭赛 B称号
- 2017腾讯实习生Android客户端开发面试总结
- zepto.js介绍
- 【Android Developers Training】 80. 管理网络使用
- PyQt4 初试牛刀二