• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 195,  comments - 30,  trackbacks - 0
            以后慢慢看
            ------------
            模板是HDOJ 2544
            我寫的是記錄每個(gè)點(diǎn)在堆中的位置IncreaseKey,也可以Relax后直接往里插,用個(gè)bool數(shù)組記錄一下

            -----
            優(yōu)化之處在于時(shí)間復(fù)雜度由n^2變?yōu)閚lgn
            -----
            #include<cstdio>
            #include<cstdlib>

            int n,m;
            int map[101][101],d[101];

            class Heap
            {
                public:
                    int handle[101];
                    void Build(int n)
                    {
                        for(int i=1;i<=n;i++) a[i]=handle[i]=i;
                        size=n;
                    }
                    void Percup(int p)
                    {
                        int temp=a[p];
                        for(;d[temp]<d[a[p>>1]];p>>=1)
                        {
                            a[p]=a[p>>1];
                            handle[a[p]]=p;
                        }
                        a[p]=temp;
                        handle[a[p]]=p;
                    }
                    int DeleteMin()
                    {
                        int val=a[1];
                        a[1]=a[size--];
                        Percdown(1);
                        handle[val]=0;
                        return val;
                    }
                    bool Empty() {return size==0;}
                private:
                    int a[101],size;
                    void Percdown(int p)
                    {
                        int temp=a[p],child;
                        for(;(p<<1)<=size;p=child)
                        {
                            child=p<<1;
                            if(child+1<=size && d[a[child+1]]<d[a[child]]) child++;
                            if(d[temp]<d[a[child]]) break;
                            a[p]=a[child];
                            handle[a[p]]=p;
                        }
                        a[p]=temp;
                        handle[a[p]]=p;
                    }
            }h;

            void init()
            {
                int i,j,c;
                for(i=1;i<=n;i++)
                {
                    for(j=1;j<=n;j++) map[i][j]=0x7fffffff;
                    d[i]=0x7fffffff;
                }
                d[1]=0;
                while(m--)
                {
                    scanf("%d%d%d",&i,&j,&c);
                    map[i][j]=map[j][i]=c;
                }
            }

            void Relax(int num)
            {
                for(int i=1;i<=n;i++)
                    if(h.handle[i] && map[num][i]!=0x7fffffff && d[i]>d[num]+map[num][i])
                    {
                        d[i]=d[num]+map[num][i];
                        h.Percup(h.handle[i]);
                    }
            }

            void dijk()
            {
                h.Build(n);
                while(!h.Empty()) Relax(h.DeleteMin());
            }

            int main()
            {
                while(scanf("%d%d",&n,&m) && n+m)
                {
                    init();
                    dijk();
                    printf("%d\n",d[n]);
                }
                system("pause");
                return 0;
            }
            ---------------------
            另一個(gè)版本
            #include <stdio.h>
            const int SIZE= 30005, MAXX=2000000000;
            int n,m,tail, dist[SIZE];
            bool mark[SIZE];
            struct Node
            {
            int id, val;
            Node* next;
            }node[SIZE];
            struct Heap{
            int id, val;
            }heap[2*SIZE];
            void insert(int a, int b, int val)
            {
            Node* p = new Node;
            p->id = a;
            p->val = val;
            p->next = node[b].next;
            node[b].next = p;
            }
            void heappush(int id, int val)
            {
            heap[++tail].id = id;
            heap[tail].val = val;
            int child, parent, temp;
            child = tail;
            while((parent = child/2)>=1)
            {
            if(heap[child].val < heap[parent].val) // child's val < parent's val ; swap ,filter
            {
            temp = heap[child].id;
            heap[child].id = heap[parent].id;
            heap[parent].id = temp;
            temp = heap[child].val;
            heap[child].val = heap[parent].val;
            heap[parent].val = temp;
            child = parent;
            }
            else
            break;
            }
            }
            int heappop()
            {
            int child, parent, temp,ret;
            ret = heap[1].id;
            heap[1].id = heap[tail].id; 
            // swap the tail to the root
            heap[1].val = heap[tail--].val;
            parent = 1;
            while((child=2*parent)<=tail)
            {
            if(child+1<=tail && heap[child+1].val < heap[child].val)
            child++;
            if(heap[child].val<heap[parent].val)
            {
            temp = heap[child].id;
            heap[child].id = heap[parent].id;
            heap[parent].id = temp;
            temp = heap[child].val;
            heap[child].val = heap[parent].val;
            heap[parent].val = temp;
            parent = child;
            }
            else
            break;
            }
            return ret;
            }
            int dijkstra(int s, int t)
            {
            int i;
            for(i=1; i<=n; i++)
            {
            dist[i] = MAXX;
            mark[i] = false;
            }
            Node* p;
            p = node[s].next;
            while(p)
            {
            dist[p->id] = p->val;
            heappush(p->id, p->val);
            p = p->next;
            }
            mark[s] = true; dist[s] = 0;
            for(i=1; i<n; i++)
            {
            int pop = heappop();
            while(mark[pop])
            pop = heappop();
            if(pop ==t || dist[pop]==MAXX)	break;
            mark[pop] = true;
            p = node[pop].next;
            while(p)
            {
            if(!mark[p->id]&&
            (dist[p->id]==MAXX || dist[pop]+p->val< dist[p->id]))
            {
            dist[p->id] = dist[pop] + p->val;
            heappush(p->id, dist[p->id]);
            }
            p = p->next;
            }
            }
            return dist[t];
            }
            int main()
            {
            int i,a,b,c;
            scanf("%d%d", &n, &m);
            for(i=1; i<=m; i++)
            {
            scanf("%d%d%d", &a, &b, &c);
            insert(a, b, c);
            }
            printf("%d\n", dijkstra(n,1));
            return 0;
            }
            
            posted on 2009-08-09 21:28 luis 閱讀(1799) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 圖論*矩陣
            <2009年8月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            色狠狠久久AV五月综合| 日本福利片国产午夜久久| 精品久久久一二三区| 18禁黄久久久AAA片| 国产精品久久毛片完整版| 国产激情久久久久影院| 四虎影视久久久免费观看| 久久精品国产亚洲av高清漫画 | 亚洲а∨天堂久久精品| 亚洲午夜久久久久久久久电影网| 久久综合综合久久97色| 久久天天婷婷五月俺也去| 国内精品久久九九国产精品| 日韩久久无码免费毛片软件| 久久久久久国产精品免费无码| 国产农村妇女毛片精品久久| 欧美黑人激情性久久| 一日本道伊人久久综合影| 久久se精品一区精品二区| 久久久久青草线蕉综合超碰| 久久精品18| 久久综合久久久| 丁香五月网久久综合| 99精品国产综合久久久久五月天| 国产成人综合久久久久久| 成人综合伊人五月婷久久| 久久久久99精品成人片试看| 久久精品无码一区二区WWW| 久久久精品人妻无码专区不卡| 7国产欧美日韩综合天堂中文久久久久 | 国产成人久久AV免费| 久久久久亚洲AV无码麻豆| 久久婷婷五月综合97色直播| 伊人久久大香线蕉成人| 久久国产AVJUST麻豆| 一97日本道伊人久久综合影院| 国产精品激情综合久久| 久久精品国产清自在天天线| 久久精品成人免费观看97| 亚洲精品高清国产一久久| 国内精品久久久久久久涩爱|