Chinaunix首页 | 论坛 | 博客
  • 博客访问: 474172
  • 博文数量: 117
  • 博客积分: 3195
  • 博客等级: 中校
  • 技术积分: 1156
  • 用 户 组: 普通用户
  • 注册时间: 2009-08-04 01:44
文章分类

全部博文(117)

文章存档

2012年(5)

2011年(5)

2010年(46)

2009年(61)

我的朋友

分类: C/C++

2010-05-30 17:55:21

以前发过这个题的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
#define1000001
#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;
}


阅读(1912) | 评论(5) | 转发(0) |
给主人留下些什么吧!~~

chinaunix网友2010-06-16 20:12:00

你跟四宝一个队的? 加油!

chinaunix网友2010-06-16 20:11:28

STL有个heap,可以直接调用的。

chhaya2010-05-31 09:00:20

确实代码量多很多, 发完才想起这个问题, 后来懒得改了。 写非递归更麻烦了啊~

chinaunix网友2010-05-31 00:55:07

你有些函数和传值调用太多~有些递归可以改为非递归~

chinaunix网友2010-05-31 00:07:06

现场赛的时候手巧heap 不太好吧,所以个人认为spfa是首选,只有需要求次短路条数的时候才会用到DIJ~~