Dijkstra+二叉堆优化

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <math.h>
  4 #include <string.h>
  5 #define MAXC 501
  6 #define MAXN 801 
  7 #define MAXM 1451 * 2
  8 #define INF 0x7FFFFFFF
  9 using namespace std;
 10 struct edge
 11 {
 12     edge *next;
 13     int t, v;
 14 } ES[MAXM];
 15 struct HeapElement
 16 {
 17     int key, value;
 18 };
 19 struct MinHeap
 20 {
 21     HeapElement H[MAXN];
 22     int size;
 23     int Position[MAXN];
 24     void init()
 25     {
 26         H[size = 0].value = -INF;
 27     }
 28     void ins(int key, int value)
 29     {
 30         int f;
 31         HeapElement p = {key, value};
 32         for (int i = ++size; p.value < H[f = i >> 1].value; i=f)
 33         {
 34             H[i] = H[f];
 35             Position[H[i].key] = i;
 36         }
 37         H[i] = p;
 38         Position[H[i].key] = i;
 39     }
 40     void decrease(int key, int value)
 41     {
 42         int f;
 43         HeapElement p = {key, value};
 44         for (int i = Position[key]; p.value < H[f = i >> 1].value; i=f)
 45         {
 46             H[i] = H[f];
 47             Position[H[i].key] = i;
 48         }
 49         H[i] = p;
 50         Position[H[i].key] = i;
 51     }
 52     void delmin()
 53     {
 54         int c;
 55         HeapElement p = H[size--];
 56         for (int i = 1; (c = i << 1) <= size; i=c)
 57         {
 58             if (c + 1 <= size && H[c + 1].value < H[c].value)
 59                 ++c;
 60             if (H[c].value < p.value)
 61             {
 62                 H[i] = H[c];
 63                 Position[H[i].key] = i;
 64             }
 65             else
 66                 break;
 67         }
 68         H[i] = p;
 69         Position[H[i].key] = i;
 70     }
 71 } H;
 72 int N, M, C, EC = -1, Ans = INF;
 73 int Cow[MAXC], sp[MAXN];
 74 edge *V[MAXN];
 75 inline void addedge(int a, int b, int c)
 76 {
 77     ES[++EC].next = V[a];
 78     ES[EC].t = b;
 79     ES[EC].v = c;
 80     V[a] = &ES[EC];
 81 }
 82 void init()
 83 {
 84     int a, b, c;
 85     scanf("%d %d %d", &C, &N, &M);
 86     for (int i = 1; i <= C; ++i)
 87         scanf("%d", &Cow[i]);
 88     for (int i = 1; i <= M; ++i)
 89     {
 90         scanf("%d %d %d", &a, &b, &c);
 91         addedge(a, b, c);
 92         addedge(b, a, c);
 93     }
 94 }
 95 void Dijkstra(int S)
 96 {
 97     sp[S] = 0;
 98     H.decrease(S, 0);
 99     for (int i = S, j; ; )
100     {
101         H.delmin();
102         for (edge *k = V[i]; k; k = k -> next)
103         {
104             if (sp[i] + k -> v < sp[j = k -> t])
105             {
106                 sp[j] = sp[i] + k -> v;
107                 H.decrease(j, sp[j]);
108             }
109         }
110         if (H.size)
111             i = H.H[1].key;
112         else
113             break;
114     }
115 }
116 void solve()
117 {
118     int Total;
119     for (int i = 1, j; i <= N; ++i)
120     {
121         H.init();
122         for (j = 1; j <= N; ++j)
123         {
124             H.ins(j, INF);
125             sp[j] = INF;
126         }
127         Total = 0;
128         Dijkstra(i);
129         for (j = 1; j <= C; ++j)
130             Total += sp[Cow[j]];
131         if (Total < Ans)
132             Ans = Total;
133     }
134 }
135 int main()
136 {
137     init();
138     solve();
139     printf("%d\n", Ans);
140     return 0;
141 }