• <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 - 21,  comments - 9,  trackbacks - 0
            此題大意為求從頂點1到頂點n的最短路徑。
            所以采用最短路徑的算法。
            想省事的話,可以使用弗洛伊德,但是n的值為10^5,這樣肯定超時。
            所以本題采用SPFA算法。見下面代碼
            #include<stdio.h>
            #include<malloc.h>
            #include<queue>
            #include<string.h>
            using namespace std;
            typedef struct node
            {
                int id;
                int distance;
                struct node *next;
            }Node,*LNode;
            int n,m;
            LNode array[100010];//鄰接鏈表
            int in_queue[100010];//記錄一個點是否在隊列中
            int between_distance[100010];//記錄起始點到兩個點之間的距離
            queue<int> q;//建立一個隊列

            void init_array()
            {
                for(int i = 0;i <= n;++i)
                {
                    array[i] = (LNode)malloc(sizeof(Node));
                    array[i]->id = i;
                    array[i]->distance = 0;
                    array[i]->next = NULL;
                }
            }

            void insert_node(LNode header,LNode &insert_node)
            {
                while(header->next != NULL)
                    header = header->next;
                insert_node->next = header->next;
                header->next = insert_node;
            }

            //任何兩點之間的距離設置為-1,表示正無窮
            void init_distance()
            {
                for(int i = 0;i <= n;++i)
                {
                    between_distance[i] = -1;
                }
                //第一個結點到自身為0
                between_distance[1] = 0;
            }

            //松弛
            void relax(int index)
            {
                if(between_distance[index] == -1)
                    return ;
                LNode header = array[index]->next;
                while(header != NULL)
                {
                    if(between_distance[header->id] > between_distance[index] + header->distance || between_distance[header->id] == -1)
                    {
                        between_distance[header->id] = between_distance[index] + header->distance;
                        if(!in_queue[header->id])
                        {
                            q.push(header->id);
                            in_queue[header->id] = 1;
                        }
                    }
                    header = header->next;
                }
            }

            void SPFA()
            {
                //第一個點入隊列
                q.push(1);
                in_queue[1] = 1;
                int index = 0;
                while(!q.empty())
                {
                    index = q.front();
                    q.pop();
                    in_queue[index] = 0;
                    relax(index);
                }
            }

            int main()
            {
                int x,y,distance;
                scanf("%d%d",&n,&m);
                init_array();
                for(int i = 0;i < m;++i)
                {
                    scanf("%d%d%d",&x,&y,&distance);
                    LNode node = (LNode)malloc(sizeof(Node));
                    node->id = y;
                    node->distance = distance;
                    insert_node(array[x],node);
                    node = (LNode)malloc(sizeof(Node));
                    node->id = x;
                    node->distance = distance;
                    insert_node(array[y],node);
                }
                init_distance();
                memset(in_queue,0,sizeof(in_queue));
                SPFA();
                if(between_distance[n] == -1)
                {
                    printf("-1\n");
                }
                else
                    printf("%d\n",between_distance[n]);
                return 0;
            }
            posted on 2012-04-06 19:59 崔佳星 閱讀(378) 評論(0)  編輯 收藏 引用 所屬分類: xoj
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久av免费天堂小草播放| 亚洲AV日韩精品久久久久久| 伊人色综合久久天天| 免费观看成人久久网免费观看| 国产免费久久精品99久久| 久久久久无码专区亚洲av| 久久伊人精品一区二区三区| 久久精品aⅴ无码中文字字幕不卡| 国产精品一区二区久久精品无码| 亚洲国产精品狼友中文久久久| 久久综合久久自在自线精品自| 久久国产视屏| 久久久久四虎国产精品| 亚洲精品无码久久毛片| 91精品国产91久久久久久青草 | 国产免费久久精品99re丫y| 中文字幕久久久久人妻| 久久久久久久综合综合狠狠| 国产精品国色综合久久| 久久久久久久精品成人热色戒| 久久精品国产99国产电影网 | 成人a毛片久久免费播放| 久久人人爽人人爽人人片AV不 | 久久精品九九亚洲精品| 一本大道久久香蕉成人网| 91精品国产91久久久久久青草 | 伊人久久大香线蕉无码麻豆| 2020最新久久久视精品爱 | 久久久久久精品成人免费图片 | 国内精品久久久久| 亚洲国产精品无码成人片久久| 久久国产成人| 久久精品视频91| 国内精品久久久久久久亚洲 | 99久久99久久精品国产片果冻 | 久久国产成人| 很黄很污的网站久久mimi色 | 国产成人无码精品久久久免费 | 久久综合五月丁香久久激情| 久久综合狠狠综合久久97色| 武侠古典久久婷婷狼人伊人|