HDU 2066 一个人的旅行【Dijkstra 】

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

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

哎= =改了好久的说= =

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

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

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 typedef long long LL;
14 const int INF = 100000000;
15 const int maxn=1010;
16 int w[maxn][maxn],v[maxn],a[maxn],b[maxn],d[maxn];
17 int t,s,n;
18 
19 void dijkstra(){
20     int i,j,k;
21     for(i=1;i<=maxn;i++) d[i]=INF;
22     for(i=1;i<=s;i++) d[a[i]]=0;
23     
24     memset(v,0,sizeof(v));
25     
26     for(i=1;i<=maxn;i++){
27         int x,m=INF;
28         for(int y=1;y<=maxn;y++) if(!v[y]&&d[y]<=m) m=d[x=y];
29         v[x]=1;
30         for(int y=1;y<=maxn;y++) d[y]=min(d[y],d[x]+w[x][y]);
31     }
32 }
33 
34 
35 int main(){
36     int i,j,k,u,v,ww;
37     while(scanf("%d %d %d",&n,&s,&t)!=EOF){
38         for(i=1;i<=maxn;i++){
39             for(j=1;j<=maxn;j++){
40                 if(i==j) w[i][j]=0;
41                 else w[i][j]=INF;
42             }
43         }
44         
45         for(i=1;i<=n;i++) {
46             scanf("%d %d %d",&u,&v,&ww);
47             if(w[u][v]>ww) w[u][v]=ww,w[v][u]=ww;            
48         }
49         
50         for(i=1;i<=s;i++) scanf("%d",&a[i]);
51         for(i=1;i<=t;i++) scanf("%d",&b[i]);
52         int idx=t;
53 
54         dijkstra();
55     
56         
57         int ans=INF;
58         t=idx;
59         
60         for(i=1;i<=t;i++) {
61           ans=min(ans,d[b[i]]);
62         }        
63         printf("%d
",ans);
64     }
65     return 0;
66 }

View Code

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