HDU1874 暢通工程續(xù)
來源：程序員人生 發(fā)布時間：2015-02-04 09:06:46 閱讀次數(shù)：3114次
鏈接：click here
題意：
某省自從實行了很多年的暢通工程計劃后，終究修建了很多路。不過路多了也不好，每次要從1個城鎮(zhèn)到另外一個城鎮(zhèn)時，都有許多種道路方案可以選擇，而某些方案要比另外一些方案行走的距離要短很多。這讓行人很困擾。
現(xiàn)在，已知出發(fā)點和終點，請你計算出要從出發(fā)點到終點，最短需要行走多少距離。
Input
本題目包括多組數(shù)據(jù)，請?zhí)幚淼轿募Y束。
每組數(shù)據(jù)第1行包括兩個正整數(shù)N和M(0<N<200,0<M<1000)，分別代表現(xiàn)有城鎮(zhèn)的數(shù)目和已修建的道路的數(shù)目。城鎮(zhèn)分別以0～N⑴編號。
接下來是M行道路信息。每行有3個整數(shù)A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城鎮(zhèn)A和城鎮(zhèn)B之間有1條長度為X的雙向道路。
再接下1行有兩個整數(shù)S,T(0<=S,T<N)，分別代表出發(fā)點和終點。
Output
對每組數(shù)據(jù)，請在1行里輸出最短需要行走的距離。如果不存在從S到T的線路，就輸出⑴.
思路：這道題題面不難理解，根據(jù)自己之前的做法，卻是返回超時。靜下心來1番仔細檢查代碼后，終究發(fā)現(xiàn)預處理數(shù)組的進程用的方法不同，返回的時間消耗就會不1樣
比如我用兩個for循環(huán)就比memset函數(shù)快的多，而且還發(fā)現(xiàn)，不知道為何定義INF的值太大時，如果用memset函數(shù)，就會出現(xiàn)意想不到的毛病。不知如何理解？，如果有人看到了有甚么想法，歡迎相互交換。
參考代碼:
#include <string.h>
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int Inf=0x3f3f3f3f;
const int maxn=202;
int cost[maxn][maxn]; //存圖
int d[maxn]; //從s動身的最短路徑
bool used[maxn]; //已使用過的圖
int V,pre,last; //頂點數(shù)
int city[maxn];
void dijkstra()
{
int i,j,k;
memset(used,0,sizeof(used));
for(i=0; i<V; i++)
d[i]=cost[pre][i];
d[pre]=0;
used[pre]=true;
while(true)
{
int v=Inf;
for(int u=0; u<V; u++)
{
if(!used[u]&&(v==Inf||d[u]<d[v]))
v=u;
}
if(v==Inf) break;
used[v]=true;
for(int u=0; u<V; u++)
{
d[u]=min(d[u],d[v]+cost[v][u]);
}
} //本來1貫的寫法，測試發(fā)現(xiàn)效力不是很高
// for(i=0; i<V; i++)
// {
// min=Inf;
// for(j=0; j<V; j++)
// if(!used[j]&&d[j]<min)
// {
// min=d[j];
// k=j;
// }
// if(min==Inf)break;
// used[k]=1;
// for(j=0; j<V; j++)
// if(!used[j]&&d[j]>d[k]+cost[j][k])
// d[j]=d[k]+cost[j][k];
// }
if(d[last]==Inf)
printf("⑴
");
else printf("%d
",d[last]);
//return d[V];
}
int main()
{
int M,i,j;
while(scanf("%d%d",&V,&M)!=EOF)
{
//memset(cost,Inf,sizeof(cost));
for(i=0; i<V; i++)
for(j=0; j<V; j++)
cost [i][j]=Inf;
int u,v,quan;
for(i=0; i<M; i++)
{
scanf("%d%d%d",&u,&v,&quan);
if(cost[u][v]>quan)
{
cost[v][u]=quan;
cost[u][v]=quan;
}
}
scanf("%d%d",&pre,&last);
dijkstra();
}
return 0;
}
測試數(shù)據(jù)
/*
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
0 0
*/
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
