80
技術社區[雲棲]
九度題目1008：最短路徑問題
題目1008：最短路徑問題時間限製：1 秒內存限製：32 兆特殊判題：否提交：5129解決：1634
題目描述：
給你n個點，m條無向邊，每條邊都有長度d和花費p，給你起點s終點t，要求輸出起點到終點的最短距離及其花
費，如果最短距離有多條路線，則輸出花費最少的。
輸入：
輸入n,m，點的編號是1~n,然後是m行，每行4個數 a,b,d,p，表示a和b之間有一條邊，且其長度為d，花費為p。
最後一行是兩個數 s,t;起點s，終點t。n和m為0時輸入結束。
(1n=1000, 0m100000, s != t)
輸出：
輸出 一行有兩個數， 最短距離及其花費。
樣例輸入：
3 2
1 2 5 6
2 3 4 5
1 3
0 0
樣例輸出：
9 11
來源：
2010年浙江大學計算機及軟件工程研究生機試真題
AC代碼：
用的迪傑斯特拉最短路徑算法
#include<stdio.h>
#include<string.h>
#define INF 0x11111111
int map[1010][1010],w[1010][1010];
int way[1010],value[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));//數組初始化為最大值
memset(w,INF,sizeof(w));
for(i=0;i<m;i++)
{
scanf("%d %d %d %d",&x,&y,&z,&v);
map[x][y]=z;//儲存正反向的路徑長度和花費
map[y][x]=z;
w[x][y]=v;
w[y][x]=v;
}
scanf("%d %d",&s,&t);
memset(way,INF,sizeof(way));//此數組儲存從s到i的長度
memset(value,INF,sizeof(value));//此數組儲存從s到i的花費
memset(flag,0,sizeof(flag));//標記路徑點是否被加入最短路徑中
flag[s]=1;//起點已經被標記為加入最短路徑
for(i=1;i<=n;i++)//開始賦值
{
way[i]=map[s][i];
value[i]=w[s][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||(way[j]==min&&value[k]<value[j]))) //如果長度相等，取花費較小的那一個
{
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]&&value[k]+w[k][j]<value[j])))
{
way[j]=way[k]+map[k][j];
value[j]=value[k]+w[k][j];
}
}
}
printf("%d %d\n",way[t],value[t]);
}
return 0;
}
最後更新：2017-04-03 08:26:11