题目描述:
有一天，孩子回来对我说：“妈妈，听说马尔代夫很不错，放假了我想去玩。”马尔代夫？我也想去！没有人不向往一场说走就走的旅行！“其实我想去的地方很多，呼伦贝尔大草原、玉龙雪山、布达拉宫、艾菲尔铁塔……”小孩子还说着他感兴趣的地方。于是我们拿出地图，标出想去的地点，然后计算最短路线，估算大约所需的时间，有了这张秘制地图，一场说走就走的旅行不是梦！
给定有向带权图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 10
Dijkstra算法，注意是有向图，而且两个地方的路不止一条。
#include<stdio.h>
#include<string.h>
#define N 1020
int e[N][N],dis[N],book[N];
int main()
{
int i,j,t,n,m,s,u,v,w,min,inf=99999999;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if(i == j)
e[i][j] = 0;
else
e[i][j] = inf;
for(i=0;i<m;i++)
{
scanf("%d%d%d", &u, &v, &w);
if(e[u][v]>w)
e[u][v] = w;
}
scanf("%d", &s);
memset(book, 0, sizeof(book));
for(i=1; i<=n; i++)
dis[i] = e[s][i];
for(i=1; i<n; i++)
{
min=inf;
for(j=1; j<=n; j++)
if(dis[j]<min && book[j] == 0)
{
min = dis[j];
u = j;
}
book[u] = 1;
for(v=1; v<=n; v++)
{
if(dis[v]>dis[u]+e[u][v])
dis[v] = dis[u]+e[u][v];
}
}
for(i=1; i<=n; i++)
{
if(dis[i] == inf)
printf("impossible ");
else
printf("%d ",dis[i]);
}
printf("
");
}
return 0;
}