8.12最短路

IDOriginTitle
Problem A HDU 2544 最短路
Problem B HDU 3790 最短路径问题
Problem C HDU 3665 Seaside
Problem D HDU 1869 六度分离
Problem E HDU 1874 畅通工程续
Problem F HDU 1317 XYZZY
Problem G HDU 4360 As long as Binbin loves Sangsang
Problem H POJ 1847 Tram
Problem I POJ 1062 昂贵的聘礼

题目就挂在这里了，还有F，G，H没有搞出、有一个大的教训就是以后不管有没有重边，一律都考虑。

A题，最水的dijkstra

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define mem(a) memset(a,0,sizeof(a))
 4 #define INF 100000007
 5 
 6 int Map[105][105],N,M,d[105],vis[105];
 7 
 8 int dijkstra(int s)
 9 {
10     mem(vis);
11     for(int i=0;i<=N;i++) d[i] = INF;
12     d[s] = 0;
13     for(int i=1;i<=N;i++)
14     {
15         int m = INF;
16         for(int j = 1;j<=N;j++)if(!vis[j] && d[j]<m)m=d[s=j];
17         vis[s] = 1;
18         for(int j=1;j<=N;j++)if(d[j] > d[s]+Map[s][j])d[j]=d[s]+Map[s][j];
19     }
20     return d[N];
21 }
22 
23 int main()
24 {
25     while(~scanf("%d%d", &N,&M) && (N||M))
26     {
27         for(int i=0;i<=N;i++)for(int j=0;j<=N;j++)
28         {
29             Map[i][j] = INF;
30         }
31         for(int i=1;i<=M;i++)
32         {
33             int a,b,c;
34             scanf("%d%d%d", &a,&b,&c);
35             Map[a][b] = Map[b][a] = c;
36         }
37         printf("%d
", dijkstra(1));
38     }
39     return 0;
40 }
View Code

B题，之前不会捉，想了一会，后来就直接模仿dijkstra的一组D值，搞了两组（坑爹的copy代码，数组大小没改WA了4次）。

当路径较短时，就直接选择较短的；

当路径相同时，选择花费较小的。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define mem(a) memset(a,0,sizeof(a))
 4 #define INF 100000007
 5 #define MIN(a,b) ((a) < (b) ? (a) : (b))
 6 
 7 int N,M,d[1005][1005],p[1005][1005],vis[1005],D[1005],P[1005];
 8 int S,E;
 9 
10 void dijkstra()
11 {
12     mem(vis);
13     for(int i=1;i<=N;i++)D[i] = P[i] = INF;
14     D[S] = P[S] = 0;
15     for(int i=1;i<=N;i++)
16     {
17         int key1 = INF,key2 = INF;
18         for(int j=1;j<=N;j++)if(!vis[j])
19         {
20             if(D[j] < key1){key1=D[S=j];key2=P[j];}
21             else if(D[j]==key1 && P[j]<key2){S=j;key2=P[j];}
22         }
23         vis[S] = 1;
24         for(int j=1;j<=N;j++)
25         {
26             if(D[j] > D[S] + d[S][j])
27             {
28                 D[j] = D[S] + d[S][j];
29                 P[j] = P[S] + p[S][j];
30             }
31             else if(D[j] == D[S] + d[S][j] && P[j] > P[S] + p[S][j])
32             {
33                 P[j] = P[S] + p[S][j];
34             }
35         }
36     }
37 }
38 
39 int main()
40 {
41     while(~scanf("%d%d", &N, &M) && (M || N))
42     {
43         for(int i=0;i<=N;i++)
44         {
45             for(int j=0;j<=N;j++)
46             {
47                 d[i][j] = p[i][j] = INF;
48             }
49         }
50         int a,b,dist,price;
51         for(int i=0;i<M;i++)
52         {
53             scanf("%d%d%d%d", &a,&b,&dist,&price);
54             if(d[a][b] > dist)
55             {
56                 d[a][b] = d[b][a] = dist;
57                 p[a][b] = p[b][a] = price;
58             }
59             else if(d[a][b] == dist && p[a][b] > price)
60             {
61                 d[a][b] = d[b][a] = dist;
62                 p[a][b] = p[b][a] = price;
63             }
64         }
65         scanf("%d%d", &S,&E);
66         dijkstra();
67         printf("%d %d
", D[E],P[E]);
68     }
69     return 0;
70 }
View Code

C题，从没做过数据这么水的题，尼玛N<=10！！！想怎么搞就怎么搞。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define mem(a) memset(a,0,sizeof(a))
 4 #define INF 100000007
 5 
 6 int Map[20][20],N,d[20],vis[20],End[20];
 7 
 8 void dijkstra(int s)
 9 {
10     for(int i=0;i<=N;i++) d[i] = INF;
11     d[s] = 0;
12     for(int i=0;i<N;i++)
13     {
14         int m = INF;
15         for(int j = 0;j<N;j++)if(!vis[j] && d[j]<m)m=d[s=j];
16         vis[s] = 1;
17         for(int j=0;j<N;j++)if(d[j] > d[s]+Map[s][j])d[j]=d[s]+Map[s][j];
18     }
19 }
20 
21 int main()
22 {
23     while(~scanf("%d", &N))
24     {
25         mem(End); mem(vis);
26         for(int i=0;i<=N;i++)for(int j=0;j<=N;j++)
27         {
28             Map[i][j] = INF;
29         }
30         int M,e,p;
31         for(int i=0;i<N;i++)
32         {
33             scanf("%d%d", &M, &End[i]);
34             for(int j=0;j<M;j++)
35             {
36                 scanf("%d%d", &e,&p);
37                 if(Map[i][e] > p) Map[i][e] = Map[e][i] = p;
38             }
39         }
40         dijkstra(0);
41         int ans = INF;
42         for(int i=0;i<N;i++)if(End[i])
43         {
44             if(ans > d[i]) ans = d[i];
45         }
46         printf("%d
", ans);
47     }
48     return 0;
49 }
View Code

D题，简单的floyd

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define mem(a) memset(a,0,sizeof(a))
 4 #define INF 100000007
 5 
 6 int N,M,d[105][105];
 7 
 8 void flyod()
 9 {
10     for(int k=0;k<N;k++)
11     {
12         for(int i=0;i<N;i++)
13         {
14             for(int j=0;j<N;j++)
15             {
16 
17                 if(d[i][j] > d[i][k] + d[k][j])
18                 {
19                     d[i][j] = d[i][k] + d[k][j];
20                 }
21             }
22         }
23     }
24 }
25 
26 int main()
27 {
28     while(~scanf("%d%d", &N,&M))
29     {
30         for(int i=0;i<=N;i++)for(int j=0;j<=N;j++)
31         {
32             d[i][j] = INF;
33         }
34         int A,B;
35         for(int i=0;i<M;i++)
36         {
37             scanf("%d%d", &A,&B);
38             d[A][B] = d[B][A] = 1;
39         }
40         flyod();
41         int ans = 1;
42         for(int i=0;i<N && ans;i++)
43         {
44             for(int j=i+1;j<N && ans;j++)
45             {
46                 if(d[i][j] > 7)ans = 0;
47             }
48         }
49         printf("%s
",ans? "Yes":"No");
50     }
51     return 0;
52 }
View Code

E题，floyd可以过，dijkstra也可以

flyod

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<map>
 5 #include<vector>
 6 #include<set>
 7 #include<stack>
 8 #include<queue>
 9 #include<algorithm>
10 #include<stdlib.h>
11 using namespace std;
12 #define MAX(a,b) (a > b ? a : b)
13 #define MIN(a,b) (a < b ? a : b)
14 #define MAXN  10000001
15 #define INF 1000000007
16 #define mem(a) memset(a,0,sizeof(a))
17 
18 int w[200][200];
19 int n;
20 
21 void floyd()
22 {
23     for(int k=0;k<n;k++)
24     {
25         for(int i=0;i<n;i++)
26         {
27             for(int j=0;j<n;j++)
28             {
29                 w[i][j] = MIN(w[i][j], w[i][k]+w[k][j]);
30             }
31         }
32     }
33 }
34 
35 int main()
36 {
37     //freopen("in.txt","r",stdin);
38     //freopen("out.txt","w",stdout);
39     int m;
40     while(~scanf("%d%d",&n,&m))
41     {
42         for(int i=0;i<n;i++)
43         {
44             for(int j=0;j<n;j++)
45             {
46                 w[i][j]=INF;
47             }
48         }
49 
50         int a,b,x;
51         for(int i=0;i<m;i++)
52         {
53             scanf("%d%d%d",&a,&b,&x);
54             if(w[a][b]>x)w[a][b] = w[b][a] = x;
55         }
56         int s,t;
57         scanf("%d%d",&s,&t);
58         if(s==t){printf("0
");continue;}
59 
60         floyd();
61 
62         printf("%d
",w[s][t]==INF?-1:w[s][t]);
63     }
64     return 0;
65 }
View Code

dijkstra

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define mem(a) memset(a,0,sizeof(a))
 4 #define INF 100000007
 5 
 6 int Map[205][205],N,M,d[205],vis[205],S,E;
 7 
 8 int dijkstra(int s)
 9 {
10     mem(vis);
11     for(int i=0;i<=N;i++) d[i] = INF;
12     d[s] = 0;
13     for(int i=0;i<N;i++)
14     {
15         int m = INF;
16         for(int j = 1;j<=N;j++)if(!vis[j] && d[j]<m)m=d[s=j];
17         vis[s] = 1;
18         for(int j=1;j<=N;j++)if(d[j] > d[s]+Map[s][j])d[j]=d[s]+Map[s][j];
19     }
20     return d[E+1];
21 }
22 
23 int main()
24 {
25     while(~scanf("%d%d", &N,&M))
26     {
27         for(int i=0;i<=N;i++)for(int j=0;j<=N;j++)
28         {
29             Map[i][j] = INF;
30         }
31         for(int i=1;i<=M;i++)
32         {
33             int a,b,c;
34             scanf("%d%d%d", &a,&b,&c);
35             if(Map[a+1][b+1] > c)Map[a+1][b+1] = Map[b+1][a+1] = c;
36         }
37         scanf("%d%d", &S,&E);
38         int ans = dijkstra(S+1);
39         printf("%d
", ans == INF ? -1 : ans);
40     }
41     return 0;
42 }
View Code

I题，见之前写的博客

http://www.cnblogs.com/gj-Acit/p/3222969.html

下面是比赛时候的代码

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define mem(a) memset(a,0,sizeof(a))
 4 #define INF 100000007
 5 #define MIN(a,b) ((a) < (b) ? (a) : (b))
 6 
 7 int N,M,d[105],price[105][105],level[105],vis[105],X;
 8 
 9 
10 int dijkstra()//返回0到1的最短路
11 {
12     for(int i=1;i<=N;i++) d[i] = price[i][i];
13     for(int i=1;i<=N;i++)
14     {
15         int m = INF,s;
16         for(int j=1;j<=N;j++)if(!vis[j] && d[j]<m) m=d[s=j];
17         vis[s]=1;
18         for(int j=1;j<=N;j++)if(!vis[j] && d[j]>d[s]+price[s][j])d[j]=d[s]+price[s][j];
19     }
20     return d[1];
21 }
22 
23 int main()
24 {
25     while(~scanf("%d%d", &M, &N))
26     {
27         for(int i=0;i<=N;i++)for(int j=0;j<=N;j++)
28         {
29             price[i][j] = INF;
30         }
31         int A,P;
32         for(int i=1;i<=N;i++)
33         {
34             scanf("%d%d%d", &price[i][i],&level[i],&X);
35             for(int j=0;j<X;j++)
36             {
37                 scanf("%d%d", &A, &P);
38                 price[A][i] = P;
39             }
40         }
41         int ans = INF;
42         for(int i=1;i<=N;i++)
43         {
44             for(int j=1;j<=N;j++)
45             {
46                 if(level[j]>level[i] || level[i]-level[j]>M) vis[j] = 1;
47                 else vis[j] = 0;
48             }
49             int flag = dijkstra();
50             ans = MIN(ans, flag);
51         }
52         printf("%d
", ans);
53     }
54     return 0;
55 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/gj-Acit/p/3254347.html