首页 > 代码库 > ccf20170304地铁修建_Solution

ccf20170304地铁修建_Solution

ccf20170304地铁修建_Solution

这里最短路为所以从点1到点n的路径中最长的道路的长度。

因为1 ≤ n ≤ 100000,1 ≤ m ≤ 200000,属于稀疏图,所以使用Spfa(循环队列)较适合,如果使用dijkstra需要堆优化。

 

其实这道题用并查集最好,对所有道路长度从小到大排序,依次添加道路,直到点1和点n相连(属于同一个集合)。

 

1.并查集

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define maxn 100000
 4 #define maxm 200000
 5 
 6 //并查集 UnionFind
 7 //171s
 8 
 9 struct node
10 {
11     long x,y,len;
12 };
13 
14 long father[maxn+1];
15 
16 long cmp(const void *a,const void *b)
17 {
18     return (*(struct node *)a).len-(*(struct node *)b).len;
19 }
20 
21 long getfather(long d)
22 {
23     if (father[d]==d)
24         return d;
25     father[d]=getfather(father[d]);
26     return father[d];
27 }
28 
29 int main()
30 {
31     long n,m,i,u,v;
32     struct node *road=(struct node *) malloc (sizeof(struct node)*(maxm+1));
33     scanf("%ld%ld",&n,&m);
34     for (i=1;i<=m;i++)
35         scanf("%ld%ld%ld",&road[i].x,&road[i].y,&road[i].len);
36     qsort(&road[1],m,sizeof(struct node),cmp);
37     for (i=1;i<=n;i++)
38         father[i]=i;
39     //边从小到大 加入图中,直到1到n可达
40     //每次加边(x,y) father[y]=x
41     for (i=1;i<=m;i++)
42     {
43         u=getfather(road[i].x);
44         v=getfather(road[i].y);
45         father[v]=u;
46 
47         //每一次判断1,n的父亲是否相同,如果是,即1到n可达
48         if (getfather(father[1])==getfather(father[n]))
49             break;
50     }
51     //即1到n必经过该边i,而该边长度最长
52     printf("%ld\n",road[i].len);
53     return 0;
54 }

 

2.Spfa(循环队列)

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <malloc.h>
  4 #include <stdbool.h>
  5 #define maxn 100000
  6 #define maxm 200000
  7 #define maxc 1000000
  8 
  9 long max(long a,long b)
 10 {
 11     if (a>b)
 12         return a;
 13     else
 14         return b;
 15 }
 16 
 17 int main()
 18 {
 19     struct node
 20     {
 21         long d,len;
 22         struct node *next;
 23     };
 24     long n,m,head,tail,d,value,i,a,b,c;
 25     long *dis=(long *) malloc (sizeof(long)*(maxn+1));
 26     //循环队列
 27     long *line=(long *) malloc (sizeof(long)*(maxn+1));
 28     bool *vis=(bool *) malloc (sizeof(bool)*(maxn+1));
 29     //本身已经是struct node *point,创建数组再加"*"
 30     struct node **point=(struct node **) malloc (sizeof(struct node *)*(maxn+1));
 31     struct node *t;
 32     scanf("%ld%ld",&n,&m);
 33 
 34     for (i=1;i<=n;i++)
 35     {
 36         point[i]=NULL;
 37         //1 ≤ c ≤ 1000000
 38         //max<=c
 39         dis[i]=maxc;
 40         vis[i]=true;
 41     }
 42     for (i=1;i<=m;i++)
 43     {
 44         scanf("%ld%ld%ld",&a,&b,&c);
 45         //build a
 46         t=(struct node *) malloc (sizeof(struct node));
 47         t->d=b;
 48         t->len=c;
 49         if (point[a]!=NULL)
 50             t->next=point[a];
 51         else
 52             t->next=NULL;
 53         point[a]=t;
 54         //build b
 55         t=(struct node *) malloc (sizeof(struct node));
 56         t->d=a;
 57         t->len=c;
 58         if (point[b]!=NULL)
 59             t->next=point[b];
 60         else
 61             t->next=NULL;
 62         point[b]=t;
 63     }
 64     dis[1]=0;
 65     vis[1]=false;
 66     line[1]=1;
 67     //head=front-1 牺牲一个位置 front为队列头位置
 68     head=0;
 69     tail=1;
 70     //这里的循环队列不用判断空或者溢出
 71     //因为如果那样的话,已经不能用了。
 72     //不存在空的情况。而数组要开的足够大,使队列不溢出。
 73     while (head!=tail)
 74     {
 75         //head++;
 76         //队列为0~n
 77         head++;
 78         if (head==n+1)
 79             head=0;
 80         d=line[head];
 81         t=point[d];
 82         while (t)
 83         {
 84             if (dis[d]<t->len)
 85                 value=http://www.mamicode.com/t->len;
 86             else
 87                 value=http://www.mamicode.com/dis[d];
 88             if (value<dis[t->d])
 89             {
 90                 dis[t->d]=value;
 91                 //如果该点未被放在队列里,则入队;否则不入队
 92                 //即在队列里的点都不重复
 93                 //则队列(tail-head)最多有n+1个数(n个点+空位置(head))
 94                 if (vis[t->d])
 95                 {
 96                     //tail++;
 97                     tail++;
 98                     if (tail==n+1)
 99                         tail=0;
100                     line[tail]=t->d;
101                     vis[t->d]=false;
102                 }
103             }
104             t=t->next;
105         }
106         vis[d]=true;
107     }
108     printf("%ld\n",dis[n]);
109     return 0;
110 }

 

3.dijkstra(80 Points)

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <malloc.h>
 4 #include <stdbool.h>
 5 #define maxn 100000
 6 #define maxm 200000
 7 #define maxc 1000000
 8 #define maxdist 1000000000
 9 
10 //裸dijkstra 80分 超时
11 
12 long max(long a,long b)
13 {
14     if (a>b)
15         return a;
16     else
17         return b;
18 }
19 
20 int main()
21 {
22     struct node
23     {
24         long d,len;
25         struct node *next;
26     };
27     struct node **point=(struct node **) malloc (sizeof(struct node *)*(maxn+1));
28     struct node *p;
29     bool *vis=(bool *) malloc (sizeof(bool)*(maxn+1));
30     long *dist=(long *) malloc (sizeof(long)*(maxn+1));
31     long n,m,i,j,a,b,c,d,value,mindist;
32     scanf("%ld%ld",&n,&m);
33     for (i=1;i<=n;i++)
34     {
35         point[i]=NULL;
36         dist[i]=maxc;
37         vis[i]=true;
38     }
39     for (i=1;i<=m;i++)
40     {
41         scanf("%ld%ld%ld",&a,&b,&c);
42         //build a
43         p=(struct node *) malloc (sizeof(struct node));
44         p->d=b;
45         p->len=c;
46         if (point[a]!=NULL)
47             p->next=point[a];
48         else
49             p->next=NULL;
50         point[a]=p;
51         //build b
52         p=(struct node *) malloc (sizeof(struct node));
53         p->d=a;
54         p->len=c;
55         if (point[b]!=NULL)
56             p->next=point[b];
57         else
58             p->next=NULL;
59         point[b]=p;
60     }
61     for (i=1;i<=n;i++)
62     {
63         vis[i]=true;
64         dist[i]=maxdist;
65     }
66     //从点1开始
67     dist[1]=0;
68     d=1;
69     vis[1]=false;
70     for (i=1;i<n;i++)
71     {
72         p=point[d];
73         while (p)
74         {
75             if (dist[d]<p->len)
76                 value=http://www.mamicode.com/p->len;
77             else
78                 value=http://www.mamicode.com/dist[d];
79             if (value<dist[p->d])
80                 dist[p->d]=value;
81             p=p->next;
82         }
83         mindist=maxdist;
84         for (j=2;j<=n;j++)
85             if (vis[j] && dist[j]<mindist)
86             {
87                 mindist=dist[j];
88                 d=j;
89             }
90         //从点n结束
91         if (d==n)
92             break;
93         vis[d]=false;
94     }
95     printf("%ld\n",dist[n]);
96     //最小堆优化
97     return 0;
98 }

 

4.dijkstra堆优化

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <malloc.h>
 4 #include <stdbool.h>
 5 #define maxn 100000
 6 #define maxm 200000
 7 #define maxc 1000000
 8 #define maxdist 1000000000
 9 
10 //裸dijkstra 80分 超时
11 
12 long max(long a,long b)
13 {
14     if (a>b)
15         return a;
16     else
17         return b;
18 }
19 
20 int main()
21 {
22     struct node
23     {
24         long d,len;
25         struct node *next;
26     };
27     struct node **point=(struct node **) malloc (sizeof(struct node *)*(maxn+1));
28     struct node *p;
29     bool *vis=(bool *) malloc (sizeof(bool)*(maxn+1));
30     long *dist=(long *) malloc (sizeof(long)*(maxn+1));
31     long n,m,i,j,a,b,c,d,value,mindist;
32     scanf("%ld%ld",&n,&m);
33     for (i=1;i<=n;i++)
34     {
35         point[i]=NULL;
36         dist[i]=maxc;
37         vis[i]=true;
38     }
39     for (i=1;i<=m;i++)
40     {
41         scanf("%ld%ld%ld",&a,&b,&c);
42         //build a
43         p=(struct node *) malloc (sizeof(struct node));
44         p->d=b;
45         p->len=c;
46         if (point[a]!=NULL)
47             p->next=point[a];
48         else
49             p->next=NULL;
50         point[a]=p;
51         //build b
52         p=(struct node *) malloc (sizeof(struct node));
53         p->d=a;
54         p->len=c;
55         if (point[b]!=NULL)
56             p->next=point[b];
57         else
58             p->next=NULL;
59         point[b]=p;
60     }
61     for (i=1;i<=n;i++)
62     {
63         vis[i]=true;
64         dist[i]=maxdist;
65     }
66     //从点1开始
67     dist[1]=0;
68     d=1;
69     vis[1]=false;
70     for (i=1;i<n;i++)
71     {
72         p=point[d];
73         while (p)
74         {
75             if (dist[d]<p->len)
76                 value=http://www.mamicode.com/p->len;
77             else
78                 value=http://www.mamicode.com/dist[d];
79             if (value<dist[p->d])
80                 dist[p->d]=value;
81             p=p->next;
82         }
83         mindist=maxdist;
84         for (j=2;j<=n;j++)
85             if (vis[j] && dist[j]<mindist)
86             {
87                 mindist=dist[j];
88                 d=j;
89             }
90         //从点n结束
91         if (d==n)
92             break;
93         vis[d]=false;
94     }
95     printf("%ld\n",dist[n]);
96     //最小堆优化
97     return 0;
98 }

 

ccf20170304地铁修建_Solution