HDU 2066 一个人的旅行【Dijkstra 】

时间：2024-11-03 12:06:08

题意：给出s个起点，d个终点，问从这些起点到达终点的最短距离

因为有多个起点，所以把这多个起点的值设为0

哎= =改了好久的说= =

是因为在代码里面的t,不知道为什么调用dijkstra()函数之后就会变成INF的值-

后来先保存下t的值，再调用----------555555555

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int INF = ;

 const int maxn=;

 int w[maxn][maxn],v[maxn],a[maxn],b[maxn],d[maxn];

 int t,s,n;

 void dijkstra(){

     int i,j,k;

     for(i=;i<=maxn;i++) d[i]=INF;

     for(i=;i<=s;i++) d[a[i]]=;

     memset(v,,sizeof(v));

     for(i=;i<=maxn;i++){

         int x,m=INF;

         for(int y=;y<=maxn;y++) if(!v[y]&&d[y]<=m) m=d[x=y];

         v[x]=;

         for(int y=;y<=maxn;y++) d[y]=min(d[y],d[x]+w[x][y]);

     }

 }

 int main(){

     int i,j,k,u,v,ww;

     while(scanf("%d %d %d",&n,&s,&t)!=EOF){

         for(i=;i<=maxn;i++){

             for(j=;j<=maxn;j++){

                 if(i==j) w[i][j]=;

                 else w[i][j]=INF;

             }

         }

         for(i=;i<=n;i++) {

             scanf("%d %d %d",&u,&v,&ww);

             if(w[u][v]>ww) w[u][v]=ww,w[v][u]=ww;

         }

         for(i=;i<=s;i++) scanf("%d",&a[i]);

         for(i=;i<=t;i++) scanf("%d",&b[i]);

         int idx=t;

         dijkstra();

         int ans=INF;

         t=idx;

         for(i=;i<=t;i++) {

           ans=min(ans,d[b[i]]);

         }

         printf("%d\n",ans);

     }

     return ;

 }

dijkstra的第一题= = go--go--g0

相关文章