生活随笔
收集整理的這篇文章主要介紹了
HDU杭电2066 - 一个人的旅行（Dijkstra算法）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
2018-5-1
今天抽時間看了最短路的幾種算法：
這道題目用的是Dijkstra算法，算法的主要思想是按照路徑長度遞增的次序產生最短路徑。
對于這個題目而言，需要注意的是：
1）賦值是雙向的，比如說a，b之間有一條要花費time時間的路，那么我們需要將x[a][b]與x[b][a]都賦值為time。
2）有重邊：對于這種情況我們需要取最小的邊。
3）多源轉換為單源：其實也就等同于0點到所有的起始點的距離為0，可以轉換成只要求出以0為起始點的到所有目標點的距離的最小值。
#include<iostream>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
const int N =
1000;
bool vis[N+
1];
int target[N+
1];
int dis[N+
1],x[N+
1][N+
1],start[N+
1];
int t,s,d,n,res;
void dijkstra(){
int i,j,min_dis,min_point;
for (i=
1;i<=n;i++) dis[i]=inf;vis[
0]=
true;
for (i=
0;i<=n;i++){dis[i]=x[
0][i];}
for (i=
0;i<n;i++){min_dis=inf;min_point=
0;
for (j=
1;j<=n;j++){
if (!vis[j]&&dis[j]<min_dis){min_dis=dis[j];min_point=j;}} vis[min_point]=
true;
for (j=
1;j<=n;j++){
if (!vis[j]&&(x[min_point][j]+min_dis<dis[j])){dis[j]=x[min_point][j]+min_dis;}}}
}
int main(){
int i,j,a,b,tim;
while (
cin>>t>>s>>d){
for (i=
0;i<=N;i++){
for (j=
0;j<=N;j++){x[i][j]=inf;}}
memset(vis,
false,
sizeof(vis));n=
0;res=inf;
for (i=
1;i<=t;i++){
cin>>a>>b>>tim;x[a][b]=x[a][b]<tim?x[a][b]:tim;x[b][a]=x[a][b]<tim?x[a][b]:tim;n=max(max(a,b),n);}
for (i=
1;i<=s;i++){
cin>>start[i];x[
0][start[i]]=
0;x[start[i]][
0]=
0;}
for (i=
1;i<=d;i++){
cin>>target[i];}dijkstra();
for (i=
1;i<=d;i++){res=min(res,dis[target[i]]);}
cout<<res<<endl;}
return 0;
}
總結
以上是生活随笔為你收集整理的HDU杭电2066 - 一个人的旅行（Dijkstra算法）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
