hdu 2544 2066 1874 2680

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define maxn 110
 4 #define INF 0x7ffffff
 5 #define Max(a,b) a>b?a:b
 6 int graph[maxn][maxn];
 7 int vis[maxn];
 8 int dis[maxn];
 9 int n,m;
10 void dijkstra()
11 {
12     int min,now;
13     memset(vis,0,sizeof(vis));
14     dis[1]=0;
15     vis[1]=1;
16     for(int i=2;i<=n;i++)
17     {
18         dis[i]=graph[1][i];
19     }
20     for(int i=2;i<=n;i++)
21     {
22         min=INF;
23         for(int j=1;j<=n;j++)
24         {
25             if(!vis[j]&&min>dis[j])
26             {
27                 min=dis[j];
28                 now=j;
29             }
30         }
31         vis[now]=1;
32         for(int j=1;j<=n;j++)
33         {
34             if(!vis[j]&&min+graph[now][j]<dis[j])
35             dis[j]=min+graph[now][j];
36         }
37     }
38     
39 }
40 int main()
41 {
42     int a,b,c;
43     while(~scanf("%d%d",&n,&m))
44     {
45         for(int i=1;i<=n;i++)
46         for(int j=1;j<=n;j++)
47         graph[i][j]=INF;
48         if(n==0&&m==0) break;
49         for(int i=1;i<=m;i++)
50         {
51             scanf("%d%d%d",&a,&b,&c);
52             if(graph[a][b]>c) graph[a][b]=graph[b][a]=c;
53         }
54         dijkstra();
55         printf("%d\n",dis[n]);
56     }
57 }

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define maxn 1010
 4 #define INF 0x7ffffff
 5 #define Max(a,b) a>b?a:b
 6 int graph[maxn][maxn];
 7 int vis[maxn];
 8 int dis[maxn];
 9 int m;
10 int s,t;
11 void dijkstra(int start)
12 {
13     int min,now;
14     memset(vis,0,sizeof(vis));
15     
16     for(int i=1;i<=maxn;i++)
17     {
18         dis[i]=graph[start][i];
19     }
20     dis[start]=0;
21     vis[start]=1;
22     for(int i=2;i<=maxn;i++)
23     {
24         min=INF;
25         for(int j=1;j<=maxn;j++)
26         {
27             if(!vis[j]&&min>dis[j])
28             {
29                 min=dis[j];
30                 now=j;
31             }
32         }
33         if(min==INF) break;
34         vis[now]=1;
35         for(int j=1;j<=maxn;j++)
36         {
37             if(!vis[j]&&min+graph[now][j]<dis[j])
38             dis[j]=min+graph[now][j];
39         }
40     }
41     
42 }
43 int main()
44 {
45     int a,b,c;
46     int start;
47     int end;
48     while(~scanf("%d%d%d",&m,&s,&t))
49     {
50         for(int i=1;i<=maxn;i++)
51         for(int j=1;j<=maxn;j++)
52         graph[i][j]=INF;
53         for(int i=1;i<=m;i++)
54         {
55             scanf("%d%d%d",&a,&b,&c);
56             if(graph[a][b]>c) graph[a][b]=graph[b][a]=c;
57         }
58         int min=INF;
59         int aa[maxn];
60         int bb[maxn];
61         for(int i=0;i<s;i++)
62         scanf("%d",&aa[i]);
63         for(int j=0;j<t;j++)
64         scanf("%d",&bb[j]);
65         for(int i=0;i<s;i++)
66         {
67             dijkstra(aa[i]);
68             for(int j=0;j<t;j++)
69             {
70                 if(min>dis[bb[j]]) min=dis[bb[j]];
71             }
72         }
73         
74         if(min==INF) printf("-1\n");
75         else 
76         printf("%d\n",min);
77     }
78 }

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define maxn 210
 4 #define INF 0x7ffffff
 5 #define Max(a,b) a>b?a:b
 6 int graph[maxn][maxn];
 7 int vis[maxn];
 8 int dis[maxn];
 9 int n,m;
10 int s,t;
11 void dijkstra()
12 {
13     int min,now;
14     memset(vis,0,sizeof(vis));
15     
16     for(int i=0;i<n;i++)
17     {
18         dis[i]=graph[s][i];
19     }
20     dis[s]=0;
21     vis[s]=1;
22     for(int i=1;i<n;i++)
23     {
24         min=INF;
25         for(int j=0;j<n;j++)
26         {
27             if(!vis[j]&&min>dis[j])
28             {
29                 min=dis[j];
30                 now=j;
31             }
32         }
33         if(min==INF) break;
34         vis[now]=1;
35         for(int j=0;j<n;j++)
36         {
37             if(!vis[j]&&min+graph[now][j]<dis[j])
38             dis[j]=min+graph[now][j];
39         }
40     }
41     
42 }
43 int main()
44 {
45     int a,b,c;
46     
47     while(~scanf("%d%d",&n,&m))
48     {
49         for(int i=0;i<n;i++)
50         for(int j=0;j<n;j++)
51         graph[i][j]=INF;
52         //if(n==0&&m==0) break;
53         for(int i=1;i<=m;i++)
54         {
55             scanf("%d%d%d",&a,&b,&c);
56             if(graph[a][b]>c) graph[a][b]=graph[b][a]=c;
57         }
58         scanf("%d%d",&s,&t);
59         dijkstra();
60         int mm=dis[t];
61         if(mm==INF) printf("-1\n");
62         else 
63         printf("%d\n",mm);
64     }
65 }

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define maxn 1010
 4 #define INF 0x7ffffff
 5 #define Max(a,b) a>b?a:b
 6 int graph[maxn][maxn];
 7 int vis[maxn];
 8 int dis[maxn];
 9 int n,m;
10 int s,t;
11 void dijkstra()
12 {
13     int min,now;
14     memset(vis,0,sizeof(vis));
15     
16     for(int i=1;i<=n;i++)
17     {
18         dis[i]=graph[s][i];
19     }
20     dis[s]=0;
21     vis[s]=1;
22     for(int i=2;i<=n;i++)
23     {
24         min=INF;
25         for(int j=1;j<=n;j++)
26         {
27             if(!vis[j]&&min>dis[j])
28             {
29                 min=dis[j];
30                 now=j;
31             }
32         }
33         if(min==INF) break;
34         vis[now]=1;
35         for(int j=1;j<=n;j++)
36         {
37             if(!vis[j]&&min+graph[now][j]<dis[j])
38             dis[j]=min+graph[now][j];
39         }
40     }
41     
42 }
43 int main()
44 {
45     int a,b,c,d;
46     
47     while(~scanf("%d%d%d",&n,&m,&s))
48     {
49         for(int i=1;i<=n;i++)
50         for(int j=1;j<=n;j++)
51         graph[i][j]=INF;
52         //if(n==0&&m==0) break;
53         for(int i=1;i<=m;i++)
54         {
55             scanf("%d%d%d",&a,&b,&c);
56             if(graph[b][a]>c) graph[b][a]=c;//把终点作为原点，这里要注意反过来，，错了几次 
57         }
58         scanf("%d",&t);
59         int min=INF;
60         dijkstra();
61         for(int i=0;i<t;i++)
62         {
63             scanf("%d",&d);
64             
65             if(min>dis[d])
66             min=dis[d];
67         }
68         
69         if(min==INF) printf("-1\n");
70         else 
71         printf("%d\n",min);
72     }
73 }