heap+dj.txt

使用堆+链表实现dijkstra,求单源最短路

#include <iostream> 
#include <algorithm> 
using namespace std; 

const int N = 31000, M = 2500000, INF = 1000000000; 

#define left(x) ((x)<<1) 
#define right(x) (((x)<<1)+1) 
#define dad(x) ((x)>>1) 

struct data 
{ 
    int id, w; 
    data *next; 
}mem[M]; 

int mem_size, size, n, m; 
typedef data * node; 
node g[N]; 

int dist[N], heap[3*N], map[N]; 

node new_node(int id, int w) 
{ 
    mem[mem_size++] = (data){id,w,0}; 
    return mem+mem_size-1; 
} 



void heap_up(int root) 
{ 
    int t=heap[root], fa=dad(root); 
    // hint: t = heap[root], not t = root 
    while(root!=1 && dist[t] < dist[heap[fa]]) 
    { 
        heap[root] = heap[fa]; 
        map[heap[root]] = root; 
        root = fa; 
        fa = dad(root); 
    } 
    heap[root] = t; 
    map[heap[root]] = root; 
} 

void heap_down(int root) 
{ 
    int pos, t=heap[root], rc; 
    while((pos=left(root)) <= size) 
    { 
        rc = right(root); 
        if(rc <= size && dist[heap[rc]] < dist[heap[pos]]) pos  = rc; 
        if(dist[t] > dist[heap[pos]] ) 
        { 
            heap[root] = heap[pos]; 
            map[heap[root]] = root; 
        } 
        else break; 
        root = pos; 
    } 
    heap[root] = t; 
    map[heap[root]] = root; 
} 

int heap_pop() 
{ 
    int t=heap[1]; 
    heap[1]=heap[size--]; 
    map[heap[1]] = 1; 
    heap_down(1); 
    return t; 
} 

int dijkstra(int s, int t) 
{ 
    int i, j, k, u, v, tmp; 
    node p; 
    for(i = 1; i <= n; i++) 
    { 
        dist[i] = INF; 
        heap[i] = i; 
        map[i] = i; 
    } 
    size = n; 
    swap(heap[1],heap[s]); 
    swap(map[1],map[s]); 
    dist[s] = 0; 

    for(i = 1; i <= n; i++) 
    { 
        u = heap_pop(); 
        for(p = g[u]->next; p; p = p->next) 
        { 
            j = dist[u] + p->w; 
            v = p->id; 
            if(j < dist[v]) 
            { 
                dist[v] = j; 
                heap_up(map[v]); 
            } 
        } 
    } 

    return dist[t]; 
} 

int main() 
{ 
    int i, j, id, w; 
    node tmp; 
    scanf("%d%d", &n, &m); 

    mem_size=0; 
    size=0; 
    for(i = 1; i <= n; i++) g[i]= new_node(0,0); 
    // clear heap, map, dist, size if multiple tests 


    for(i = 0; i < m; i++) 
    { 
        scanf("%d%d%d",&j,&id,&w); 
        tmp = g[j]->next; 
        g[j]->next = new_node(id,w); 
        g[j]->next->next = tmp; 
    } 

    printf("%d\n", dijkstra(1, n)); 
    return 0; 
}