• <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>
            隨筆-72  評論-126  文章-0  trackbacks-0
            http://acm.hdu.edu.cn/showproblem.php?pid=2544

            #include<stdio.h>
            #define Max 1000001
            #include
            <string>
            struct Road{
                
            int dis;
                
            int to;
                
            struct Road * next;
            };
            Road map[
            1000001],*tail[1000001];
            struct Heap{
                
            int x,dis;
            }hh[
            1000001];
            bool hash[1000001];
            int n,m;
            int len;
            void PutHeap(Heap a)
            {
                
            int i;
                
            for(i=++len;hh[i>>1].dis > a.dis;i>>=1)
                    hh[i] 
            = hh[i>>1];
                hh[i] 
            = a;
            }
            Heap GetHeap()
            {
                Heap min 
            = hh[1];
                Heap last 
            = hh[len--];
                
            int i,s;
                
            for(i=1;2*i<=len;i=s)
                {
                    s 
            = i<<1;
                    
            if(s+1<=len && hh[s+1].dis < hh[s].dis)
                        s 
            ++;
                    
            if(hh[s].dis < last.dis)
                        hh[i] 
            = hh[s];
                    
            else
                        
            break;
                }
                hh[i] 
            = last;
                
            return min;
            }
            int bfs()
            {
                Heap a;
                a.x 
            = 1;
                a.dis 
            = 0;
                PutHeap(a);
                
            while(len)
                {
                    Heap min 
            = GetHeap();
                    
            if(min.x == n)
                        
            return min.dis;
                    
            int x = min.x;
                    
            if(!hash[x])
                        
            continue;
                    hash[x] 
            = false;
                    
            int dis = min.dis;

                    Road 
            *p;
                    p 
            = map[x].next;
                    
            while(p!=NULL)
                    {
                        
            int b = p->to;
                        
            if(hash[b])
                        {
                            a.x 
            = b;
                            a.dis 
            = p->dis + dis;
                            PutHeap(a);
                        }
                        p 
            = p->next;
                    }
                }
            }
            int main()
            {
                
            while(scanf("%d%d",&n,&m),n+m)
                {
                    len 
            = 0;
                    
            for(int i=1;i<=n;i++)
                    {
                        hash[i] 
            = true;
                        map[i].next 
            = NULL;
                        tail[i] 
            = &map[i];
                    }
                    
            for(i=0;i<m;i++)
                    {
                        
            int a,b,dis;
                        Road 
            *p,*q;
                        p 
            = (Road *)malloc(12);
                        q 
            = (Road *)malloc(12);

                        scanf(
            "%d%d%d",&a,&b,&dis);
                        p
            ->next = NULL;
                        p
            ->dis = dis;
                        p
            ->to = b;
                        tail[a]
            ->next = p;
                        tail[a] 
            = tail[a]->next;

                        q
            ->next = NULL;
                        q
            ->dis = dis;
                        q
            ->to = a;
                        tail[b]
            ->next = q;
                        tail[b] 
            = tail[b]->next;;
                    }
                    printf(
            "%d\n",bfs());
                }
                
            return 0;
            }
            posted on 2009-03-27 18:18 shǎ崽 閱讀(469) 評論(0)  編輯 收藏 引用
            性高湖久久久久久久久| 久久97精品久久久久久久不卡| 久久伊人精品青青草原高清| 国内精品久久国产大陆| 99久久国产综合精品成人影院 | 潮喷大喷水系列无码久久精品| 亚洲色欲久久久综合网| 香港aa三级久久三级| 综合久久给合久久狠狠狠97色| 久久婷婷五月综合国产尤物app| 国内精品久久久久久不卡影院| 久久久久久久精品成人热色戒| 国产产无码乱码精品久久鸭| 久久久久黑人强伦姧人妻| 性欧美大战久久久久久久久| 色婷婷噜噜久久国产精品12p| 久久久久亚洲Av无码专| 性做久久久久久久久浪潮| 91精品国产综合久久香蕉| 久久久久亚洲AV片无码下载蜜桃 | 爱做久久久久久| 久久天天躁狠狠躁夜夜avapp | 少妇内射兰兰久久| 狠狠色婷婷久久一区二区| 无码专区久久综合久中文字幕 | 久久国产精品国语对白| 一本一本久久A久久综合精品| 国内精品久久久久影院网站| 97久久精品无码一区二区天美| 日产精品久久久久久久| 久久久久久无码国产精品中文字幕| 国产韩国精品一区二区三区久久| 伊人久久大香线蕉AV色婷婷色| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 日韩一区二区久久久久久| 亚洲欧洲日产国码无码久久99| 中文字幕无码久久人妻| 女同久久| 国产精品亚洲综合久久| 国色天香久久久久久久小说| 久久久无码精品亚洲日韩蜜臀浪潮|