首页 > 代码库 > HDU Today（三种写法）（最短路）
HDU Today（三种写法）（最短路）
Description
经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候，XHD夫妇也退居了二线，并在风景秀美的诸暨市?浦镇陶姚村买了个房子，开始安度晚年了。
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。
徐总经常会问蹩脚的英文问路：“Can you help me?”。看着他那迷茫而又无助的眼神，热心的你能帮帮他吗？
请帮助他用最短的时间到达目的地（假设每一路公交车都只在起点站和终点站停，而且随时都会开）。
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。
徐总经常会问蹩脚的英文问路：“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，表示输入结束。
第二行有徐总的所在地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
解题思路：
题目唯一难点就是如何去表示地点，用map映射可以轻松搞定，一个地点名对应一个值，剩下的就是求最短路径。下面给出三个代码，第一个是用朴素Dijkstra写的，第二个用了Floyd，第三个用了Dijkstra + heap。感觉上运行效率差不多。。。。。
AC代码：
Dijkstra:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int maxn = 200, INF = 9999999;
int route[maxn][maxn], dist[maxn];
int Dijkstra(int n,int start,int end)
{
bool visited[maxn];
int pos = start, min;
for(int i = 1; i <= n; i++)
{
dist[i] = route[start][i];
visited[i] = 0;
}
dist[start] = 0;
visited[start] = 1;
for(int i = 1; i < n; i++)
{
min = INF;
for(int j = 1; j <= n; j++)
if((!visited[j]) && dist[j] < min)
{
pos = j;
min = dist[pos];
}
if(min == INF)
break;
visited[pos] = 1;
for(int j = 1; j <= n; j++)
if(!visited[j] && dist[pos] + route[pos][j] < dist[j])
{
dist[j] = dist[pos] + route[pos][j];
}
}
return dist[end];
}
int main()
{
int n, ans, len;
map<string,int> station;
char start[50], end[50], str_1[50], str_2[50];
while(scanf("%d", &n))
{
if(n == -1)
break;
station.clear();
for(int i = 0; i < maxn; i++)
for(int j = 0; j < maxn; j++)
route[i][j] = INF;
scanf("%s %s", start, end);
int count = 1;
station[start] = 1;
if(!station[end])
station[end] = ++count;
for(int i = 0; i < n; i++)
{
scanf("%s %s %d", str_1, str_2, &len);
if(!station[str_1])
station[str_1] = ++count;
if(!station[str_2])
station[str_2] = ++count;
if(len < route[station[str_1]][station[str_2]])
route[station[str_1]][station[str_2]] = route[station[str_2]][station[str_1]] = len;
}
ans = Dijkstra(count,station[start], station[end]);
if(ans == INF)
printf("-1\n");
else
printf("%d\n",ans);
}
return 0;
}Floyd:#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int maxn = 200, INF = 9999999;
int dist[maxn][maxn];
int Floyd(int n,int start,int end)
{
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i != k && i != j && j != k)
dist[i][j] = dist[i][j] < (dist[i][k] + dist[k][j]) ? dist[i][j] : (dist[i][k] + dist[k][j]);
if(start == end)
return 0;
return dist[start][end];
}
int main()
{
int n, ans, len;
map<string,int> station;
char start[50], end[50], str_1[50], str_2[50];
while(scanf("%d", &n))
{
if(n == -1)
break;
station.clear();
for(int i = 0; i < maxn; i++)
for(int j = 0; j < maxn; j++)
dist[i][j] = INF;
scanf("%s %s", start, end);
int count = 1;
station[start] = 1;
if(!station[end])
station[end] = ++count;
for(int i = 0; i < n; i++)
{
scanf("%s %s %d", str_1, str_2, &len);
if(!station[str_1])
station[str_1] = ++count;
if(!station[str_2])
station[str_2] = ++count;
if(len < dist[station[str_1]][station[str_2]])
dist[station[str_1]][station[str_2]] = dist[station[str_2]][station[str_1]] = len;
}
ans = Floyd(count,station[start], station[end]);
if(ans == INF)
printf("-1\n");
else
printf("%d\n",ans);
}
return 0;
}
Dijkstra + heap:#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
const int maxn = 200, INF = 9999999;
int route[maxn][maxn], dist[maxn];
struct node
{
int pos, dist;
friend bool operator < (node a, node b)
{
return a.dist > b.dist;
}
};
int Dijkstra(int n,int start,int end)
{
bool visited[maxn];
int pos;
node tmp;
tmp.pos = start;
tmp.dist = 0;
priority_queue<node> q;
for(int i = 1; i <= n; i++)
{
visited[i] = 0;
dist[i] = INF;
}
dist[start]= 0;
q.push(tmp);
while(!q.empty())
{
tmp = q.top();
q.pop();
pos = tmp.pos;
if(tmp.dist == INF)
return INF;
if(visited[pos])
continue;
visited[pos] = 1;
for(int i = 1; i <= n; i++)
if(!visited[i] && tmp.dist + route[pos][i] < dist[i])
{
dist[i] = tmp.dist + route[pos][i];
node t; t.pos = i; t.dist = dist[i];
q.push(t);
}
}
return dist[end];
}
int main()
{
int n, ans, len;
map<string,int> station;
char start[50], end[50], str_1[50], str_2[50];
while(scanf("%d", &n))
{
if(n == -1)
break;
station.clear();
for(int i = 0; i < maxn; i++)
for(int j = 0; j < maxn; j++)
route[i][j] = INF;
scanf("%s %s", start, end);
int count = 1;
station[start] = 1;
if(!station[end])
station[end] = ++count;
for(int i = 0; i < n; i++)
{
scanf("%s %s %d", str_1, str_2, &len);
if(!station[str_1])
station[str_1] = ++count;
if(!station[str_2])
station[str_2] = ++count;
if(len < route[station[str_1]][station[str_2]])
route[station[str_1]][station[str_2]] = route[station[str_2]][station[str_1]] = len;
}
ans = Dijkstra(count,station[start], station[end]);
if(ans == INF)
printf("-1\n");
else
printf("%d\n",ans);
}
return 0;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。