HDU2112-HDU Today(Floyd Dijkstra)

2024-02-10 07:18
文章标签 hdu dijkstra floyd today hdu2112

本文主要是介绍HDU2112-HDU Today(Floyd Dijkstra),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

HDU Today

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

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

Floyd算法

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int inf=0x3f3f3f3f;
const int V_MAX=153;
int e[V_MAX][V_MAX];
int main(){ios_base::sync_with_stdio(false);int n;while(cin>>n,n!=-1){for(int i=1;i<=V_MAX;i++)for(int j=1;j<=V_MAX;j++)if(i==j) e[i][j]=0;else e[i][j]=inf;map<string,int> m;string start,end,t1,t2;int t3;int q=0;cin>>start>>end;if(!m[start]) m[start]=++q;if(!m[end]) m[end]=++q;for(int i=0;i<n;i++){cin>>t1>>t2>>t3;if(!m[t1])m[t1]=++q;if(!m[t2])m[t2]=++q;e[m[t1]][m[t2]] =e[m[t2]] [m[t1]]=t3;}for(int k=1;k<=q;k++)for(int i=1;i<=q;i++)for(int j=1;j<=q;j++)e[i][j]=min(e[i][j],e[i][k]+e[k][j] );                      if(e[m[start]][m[end]]!=inf)cout<<e[m[start]][m[end]]<<endl;elsecout<<"-1"<<endl;}
}

Dijkstra算法
用Dijkstra 可以找到最短路径.

#include<cstdio>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<map>
#define INF 0x3f3f3f3f
#define maxn 153
int dist[maxn];
int last[maxn]; 
int visit[maxn];
int graph[maxn][maxn];
int fin_cnt;void init(int n){memset(visit,0,sizeof(visit));memset(last,-1,sizeof(last));dist[0]=0;visit[0]=1;for(int i=1;i<n ;i++){dist[i]  = graph[0][i];if(dist[i] !=INF)last[i]=0;}fin_cnt=1; 
}void dijkstra(int n){int Min,Min_idx;while( fin_cnt < n){Min=INF;Min_idx=-1;for(int i=1;i< n;i++){if(visit[i]==1) continue;if( dist[i] < Min )Min=dist[i],Min_idx=i;}if(Min_idx == -1)  break;visit[Min_idx] =1;fin_cnt++;for(int i=1;i<n ;i++){if(visit[i] ==1 ) continue;if(dist[Min_idx] + graph[Min_idx][i] < dist[i])last[i]=Min_idx,dist[i] = dist[Min_idx]+graph[Min_idx][i];}               } }
using namespace std;
//寻找路径 
void find_path(int i,map<int,string> reverse_m,int deep){if(i !=-1){find_path(last[i],reverse_m,deep+1);cout<<reverse_m[i+1];if(deep==0)cout<<endl;elsecout<<"->";}
}
int main(){ios_base::sync_with_stdio(false);int n;while(cin>>n,n!=-1){for(int i=0;i<maxn;i++)for(int j=0;j<maxn;j++)if(i==j) graph[i][j]=0;else graph[i][j]=INF;map<string,int> m;int q=0;string start,end,t1,t2;int t3;cin>>start>>end;if(!m[start])m[start] = ++q;if(!m[end])m[end] = ++q;for(int i=0;i<n;i++){cin>>t1>>t2>>t3;if(m[t1] ==0)m[t1]=++q;if(m[t2] ==0)m[t2]=++q;graph[m[t1]-1][m[t2]-1]=graph[m[t2]-1][m[t1]-1] = t3;   }   init(q);dijkstra(q);if(dist[m[end]-1] != INF)cout<<dist[m[end]-1]<<endl; elsecout<<-1<<endl;/*寻找路径 map<int,string> reverse_m;for(pair<string,int> x:m){string fi=x.first;int se=x.second;reverse_m[se]=fi;       }find_path(m[end]-1,reverse_m,0);*/  }
}

这篇关于HDU2112-HDU Today(Floyd Dijkstra)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/696470

相关文章

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

uva 10801(乘电梯dijkstra)

题意: 给几个电梯,电梯0 ~ n-1分别可以到达很多层楼。 换乘电梯需要60s时间。 问从0层到target层最小的时间。 解析: 将进入第0层的电梯60s也算上,最后减。 坑点是如果target为0输出0。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algori

uva 10099(floyd变式)

题意: 有一个导游要带着一群旅客从一个城市到达另一个城市,每个城市之间有最大的旅客流量限制。 问最少几趟能将这些旅客从一个城市搞到另一个城市。 解析: 用floyd找出最小流量中的最大边,然后次数就是   ceil(总人数 / 最大承载量 - 1),-1的意思是导游每次也要在车上。 ps.老司机哭晕在厕所 代码: #include <iostream>#includ

uva 10048(floyd变式)

题意: 求两个点之间经过的路径中最大噪声最小的值。 解析: floyd的变式,每次取g[i][k] g[k][j]中的大边与当前边g[i][j]比较,取小。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#includ