106
九度题目1447：最短路
题目1447：最短路
时间限制：1 秒
内存限制：128 兆
特殊判题：否
提交：1650
解决：798
题目描述：
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
输入：
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。输入保证至少存在1条商店到赛场的路线。
当输入为两个0时，输入结束。
输出：
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间。
样例输入：
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0样例输出：
3
2
迪杰斯特拉小练习
AC代码：
#include<stdio.h>
#include<string.h>
#define INF 0x11111111
int map[1010][1010];
int way[1010],flag[1010];
int main()
{
int i,j,n,m,x,y,z,v,s,t;
while(scanf("%d %d",&n,&m),n!=0&&m!=0)
{
memset(map,INF,sizeof(map));//数组初始化为最大值
for(i=0;i<m;i++)
{
scanf("%d %d %d",&x,&y,&z);
map[x][y]=z;//储存正反向的路径长度和花费
map[y][x]=z;
}
memset(way,INF,sizeof(way));//此数组储存从s到i的长度
memset(flag,0,sizeof(flag));//标记路径点是否被加入最短路径中
flag[1]=1;//起点已经被标记为加入最短路径
for(i=1;i<=n;i++)//开始赋值
{
way[i]=map[1][i];
}
for(i=1;i<n;i++)
{
int min=INF;
int k=0;
for(j=1;j<=n;j++)//找出一个距离起点最近的路径
{
if(flag[j]==0&&way[j]<min)
{
min=way[j];
k=j;
}
}
flag[k]=1;
for(j=1;j<=n;j++)//找出距离刚刚选出来的点最近的距离组成新的路径
{
if(flag[j]==0&&way[k]+map[k][j]<way[j])
{
way[j]=way[k]+map[k][j];
}
}
}
printf("%d\n",way[n]);
}
return 0;
}
佛洛伊德算法（以前写的）：
AC代码：
#include<stdio.h>
#include<string.h>
#define MAX 105 //节点最多到100
#define INF 0x11111111 //定义一个初始地址
int i,j,n,m,x,y,z;//全局变量方便操作
typedef int num[MAX][MAX];//二维数组用来存路径
typedef int per[MAX][MAX];//用来对路径进行操作
num a;//num类型的二维数组a
per b;//per类型的二维数组b
void Shortway(num &a,per &b,int n)//最短路径函数
{
int v,w,u;
for (v=0; v<n; ++v) // 各对结点之间初始已知路径及距离
{
for (w=0; w<n; ++w) {
b[v][w] = a[v][w];
}
b[v][v] = 0; // BUG 修正
}
for (u=0; u<n; ++u)
for (v=0; v<n; ++v)
for (w=0; w<n; ++w)
if (b[v][u]+b[u][w] < b[v][w]) { // 从v经u到w的一条路径更短
b[v][w] = b[v][u]+b[u][w];
}
}
int main()
{
while(scanf("%d%d",&n,&m),n!=0&&m!=0)
{
memset(a,INF,sizeof(a));//二维数组初始化,给他们一个初始地址
memset(b,INF,sizeof(b));
for(i=0;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
x--;y--;
a[x][y]=z;//将正反路径带权都储存
a[y][x]=z;
}
Shortway(a,b,n);
printf("%d\n",b[0][n-1]);//输出0到n-1的最短路径
}
return 0;
}
最后更新：2017-04-03 05:39:37