poj 1511 Invitation Cards(dij+heap)

时间：2010-05-30 来源：chhaya

以前发过这个题的SPFA版解题报告http://blog.chinaunix.net/u3/102624/showart_2065129.html
dijkstra+heap能保持稳定的解决问题的速度，而spfa在某些情况下可能并没有比普通的dij好，所以有时候没有负权的情况下，dij+heap是个不错的选择，但是我用dij+heap做这个题，却比spfa慢很多，可能写得不够好吧，有大牛路过的话希望能指点一下。

#include <stdio.h>
#include <string.h>
#define N 1000001
#define M 1000001
#define inf 0x7fffffff

/*堆中节点*/
typedef struct nnode
{
    int key; //对应图中的节点
    int dis; //距离

}nnode;
nnode hnode[N];
int conv[N]; //图中的节点对应到二叉树的位置

/*邻接表节点*/
typedef struct node
{
    int key;
    int dis;
    struct node *next;
}node;
node *vert[N], edge[M], *_vert[N], _edge[M];

int visited[N];
int heap_size = 0;

void swp(struct nnode *a, struct nnode *b)
{
    struct nnode tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void swp_int(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

//调整堆

void heapify(int i)
{
    int l = i << 1;
    int r = (i << 1) + 1;
    int min;
    if(l <= heap_size && hnode[l].dis < hnode[i].dis)
     min = l;
    else
     min = i;
    if(r <= heap_size && hnode[min].dis > hnode[r].dis)
     min = r;
    if(min != i)
    {
     swp(&hnode[i], &hnode[min]);
     conv[hnode[i].key] = i; //这个也要相应改变

     conv[hnode[min].key] = min;
     heapify(min);
    }
}

//初始化二叉查找树的节点

void init(int s, int n)
{
    int i;
    for(i=1; i<=n; i++)
    {
        hnode[i].key = i;
        hnode[i].dis = inf;
        conv[i] = i;
    }
    hnode[s].dis = 0;
}

//建树

void build(int n)
{
    int i;
    heap_size = n;
    for(i=n/2; i>=1; i--)
    {
        heapify(i);
    }
}

//取得根节点，并自顶向下调整

int get_min()
{
    int min = hnode[1].key;
    swp(&hnode[1], &hnode[heap_size]);
    conv[hnode[1].key] = 1;
    conv[hnode[heap_size].key] = heap_size;
    heap_size--;
    heapify(1);
    return min;

}

// 松弛操作

void relax(int u, node *p, node *vert[])
{
    int tmp;
    int vv = conv[p->key];
    if(hnode[vv].dis > hnode[conv[u]].dis + p->dis)
    {
        hnode[vv].dis = hnode[conv[u]].dis + p->dis;

        while(vv > 1) //节点最短距离改变了，所以树也要调整，从下往上交换

        {
            tmp = vv >> 1;
            if(hnode[tmp].dis > hnode[vv].dis)
            {
                swp(&hnode[tmp], &hnode[vv]);
                swp_int(&conv[hnode[tmp].key], &conv[hnode[vv].key]);
            }
            vv = tmp;
        }
    }
}

//核心，dijkstra算法，跟一般的一样，除了取得最小距离的点是从查找二叉树取的

//本来是O(n),改进到O(log n),于是总的复杂度为O(nlogn)

long long dij(int s, int n, node *vert[])
{

    int u, i;
    long long ans = 0;
    node *p;
    init(s, n);
    build(n);
    while(heap_size > 0)
    {
     u = get_min();
     visited[u] = 1;
     for(p=vert[u]; p; p=p->next)
     {
     if(p->dis < inf)
     relax(u, p, vert);
     }
    }

    for(i=1; i<=n; i++)
     ans += hnode[i].dis;
     return ans;
}

int main()
{

    int t, n, m;
    int a, b, c;
    int i;
    freopen("i.in", "r", stdin);
    scanf("%d", &t);
    while(t--)
    {
        for(i=1; i<N; i++)
        {
            vert[i] = NULL;
            _vert[i] = NULL;
        }
        scanf("%d%d", &n, &m);
        for (i=0; i<m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            edge[i].key = b;
            edge[i].dis = c;
            edge[i].next = vert[a];
            vert[a] = &edge[i];

            _edge[i].key = a;
            _edge[i].dis = c;
            _edge[i].next = _vert[b];
            _vert[b] = &_edge[i];
        }

        printf("%lld\n", dij(1, n, vert)+ dij(1, n, _vert));
    }
    return 0;
}