题目描述:
有一天，孩子回来对我说：“妈妈，听说马尔代夫很不错，放假了我想去玩。”马尔代夫？我也想去！没有人不向往一场说走就走的旅行！“其实我想去的地方很多，呼伦贝尔大草原、玉龙雪山、布达拉宫、艾菲尔铁塔……”小孩子还说着他感兴趣的地方。于是我们拿出地图，标出想去的地点，然后计算最短路线，估算大约所需的时间，有了这张秘制地图，一场说走就走的旅行不是梦！
给定有向带权图G =（V，Ｅ），其中每条边的权是非负实数。此外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其他各顶点的最短路径长度，这里路径长度指路上各边的权之和。
输入描述:
第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是两个整数n,c(1<n,c<1000)表示该测试数据有n个城市c条边。
随后的c行，每行有3个正整数u,v,w(0<u,v<=n, 0<w<10000),分别表示边的两个顶点编号u,v及两顶点之间的距离。
最后一行，源点的编号s(0<s<=n)。
输出描述:
对于每一组输入，输出n个整数，代表源点到其它顶点的最短距离。如果源点不能到达其他顶点输出“impossible”。
每组的输出占一行。
样例输入:
复制
2
5 11
1 5 12
5 1 8
1 2 16
2 1 29
5 2 32
2 4 13
4 2 27
1 3 15
3 1 21
3 4 7
4 3 19
5
3 5
1 2 6
1 3 13
2 1 10
2 3 4
3 1 5
1
样例输出:
8 24 23 30 0
0 6 10dijkstra算法模板题C++代码：
#include<iostream>
#include<cstdio>
using namespace std;
const int INF =
0x3f3f3f3f;
const int maxn =
1000+
10;
int mp[maxn][maxn],dis[maxn],book[maxn],node,edge;
void dijkstra(
int x){
for(
int i =
1; i <= node; i++
){
dis[i] =
mp[x][i];
book[i] =
0;
}
dis[x] =
0;
book[x] =
1;
for(
int i =
1; i <= node; i++
){
int minn = INF,t =
x;
for(
int j =
1;j <= node; j++
)
if(book[j] ==
0 && dis[j] <
minn){
minn =
dis[j];
t =
j;
}
book[t] =
1;
for(
int j =
1;j <= node; j++
){
if(book[j] ==
0 && dis[t] + mp[t][j] < dis[j] && mp[t][j] <
INF){
dis[j] = dis[t] +
mp[t][j];
}
}
}
}
int main(){
int m;
scanf("%d",&
m);
while(m--
){
scanf("%d%d",&node,&
edge);
for(
int i =
1; i <= node; i++
){
for(
int j =
1; j <= node; j++
){
mp[i][j] =
INF;
}
}
int n,v,w;
for(
int i =
1; i <= edge; i++
){
scanf("%d%d%d",&n,&v,&
w);
if(w <
mp[n][v])
mp[n][v] =
w;
}
int x;
scanf("%d",&
x);
dijkstra(x);
for(
int i =
1; i <= node; i++
){
if(dis[i] ==
INF){
cout<<
"impossible"<<
" ";
}
else{
cout<<dis[i]<<
" ";
}
}
cout<<
endl;
}
return 0;
}
转载于:https://www.cnblogs.com/Weixu-Liu/p/10633045.html
