HDU 1874 畅通工程续

求任意两点间的最短距离若不连通输出-1
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 
  5 using namespace std;
  6 
  7 const int Max = 100000001;
  8 
  9 struct N
 10 {
 11     int v,w;
 12     N *next;
 13 }*head[210];
 14 
 15 void init(int n)
 16 {
 17     for(int i = 0;i < n; i++)
 18     {
 19         head[i] = (struct N *)malloc(sizeof(struct N));
 20         head[i]->v = head[i]->w  = -1;
 21         head[i]->next = NULL;
 22     }
 23 }
 24 
 25 void link(int u,int v,int w)
 26 {
 27     N *p1,*p2,*p;
 28     for(p1 = head[u],p2 = head[u]->next; p2 != NULL; p1 = p1->next,p2 = p2->next)
 29     {
 30         if(p2->v == v)
 31         {
 32             if(p2->w > w)
 33                 p2->w = w;
 34             return;
 35         }
 36         if(p1->v < v && v < p2->v)
 37         {
 38             p = (struct N *)malloc(sizeof(struct N));
 39             p->v = v;
 40             p->w = w;
 41             p->next = p1->next;
 42             p1->next = p;
 43             return;
 44         }
 45     }
 46     p = (struct N *)malloc(sizeof(struct N));
 47     p->v = v;
 48     p->w = w;
 49     p->next = NULL;
 50     p1->next = p;
 51     return;
 52 }
 53 
 54 int mark[1000];
 55 
 56 void find(int n,int start)
 57 {
 58     int q[10001],t;
 59     int s,e,i;
 60     for(i = 0;i < n; i++)
 61         mark[i] = Max;
 62     N *p;
 63     for(s = 0,e = 0,p = head[start]->next; p != NULL; p = p->next)
 64     {
 65         q[e++] = p->v;
 66         mark[p->v] = p->w;
 67     }
 68     while(s != e)
 69     {
 70         t = q[s];
 71         s++;
 72         for(p = head[t]->next; p != NULL; p = p->next)
 73         {
 74             if(mark[t] + p->w < mark[p->v])
 75             {
 76                 mark[p->v] = mark[t] + p->w;
 77                 q[e++] = p->v;
 78             }
 79         }
 80     }
 81 }
 82 
 83 int hash[210];
 84 
 85 int f(int x)
 86 {
 87     while(x != hash[x])
 88     {
 89         x = hash[x];
 90     }
 91     return x;
 92 }
 93 
 94 void merge(int u,int v)
 95 {
 96     int fu = f(u);
 97     int fv = f(v);
 98     hash[fu] = fv;
 99 }
100 
101 int main()
102 {
103     int n,m,i,u,v,w,s,t;
104     while(scanf("%d %d",&n,&m) != EOF)
105     {
106         init(n);
107         for(i = 0;i < n; i++)
108         {
109             hash[i]= i;
110         }
111         for(i = 0;i < m;i++)
112         {
113             scanf("%d %d %d",&u,&v,&w);
114             link(v,u,w);
115             link(u,v,w);
116             merge(u,v);
117         }
118         scanf("%d %d",&s,&t);
119         int fs = f(s);
120         int ft = f(t);
121         if(fs != ft) printf("-1\n");
122         else
123         {
124             if(s == t)
125                 printf("0\n");
126             else
127             {
128                 find(n,s);
129                 printf("%d\n",mark[t]);
130             }
131         }
132     }
133     return 0;
134 }