最短路

 1 //dijkstra
 2 #include<queue>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 const int MAXN = 100;
 8 const int MAXM = 10000;
 9 ////////////////////////////////////////////////
10 struct dij_edge{
11     int from, to, next, val;
12 }dij_e[MAXM];
13 
14 struct Node{
15     int x, d;
16     Node(){}
17     Node( int a, int b ): x( a ), d( b ){}
18     bool operator < ( Node a ) const{
19         return d > a.d;
20     }
21 };
22 
23 int dij_h[MAXN], dij_dis[MAXN], dij_cnt;
24 
25 void dij_init(){
26     dij_cnt = 0;
27     memset( dij_h, -1, sizeof( dij_h ) );
28 }
29 
30 void dij_add( int from, int to, int val ){
31     dij_e[dij_cnt].from = from;
32     dij_e[dij_cnt].to = to;
33     dij_e[dij_cnt].val = val;
34     dij_e[dij_cnt].next = dij_h[from];
35     dij_h[from] = dij_cnt++;
36 }
37 
38 void dij( dij_edge *edge, int *dis, int *h, int s ){
39     dis[s] = 0;
40 
41     priority_queue<Node> Q;
42     Q.push( Node( s, dis[s] ) );
43 
44     while( !Q.empty() ){
45         Node temp = Q.top(); Q.pop();
46         int x = temp.x;
47         if( temp.d > dis[x] ) continue;
48         for( int k = h[x]; k != -1; k = edge[k].next ){
49             int y = edge[k].to;
50             if( dis[y] > dis[x] + edge[k].val ){
51                 dis[y] = dis[x] + edge[k].val;
52                 Q.push( Node( y, dis[y] ) );
53             }
54         }
55     }
56 }
57 
58 //dij( dij_e, dij_dis, dij_h, source );
59 int main(){
60     return 0;
61 }