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