• <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)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久99热这里只频精品6| 色综合久久久久综合体桃花网| 亚洲av日韩精品久久久久久a| 精品多毛少妇人妻AV免费久久| 中文字幕无码久久人妻| 日韩精品久久久久久久电影蜜臀| 午夜精品久久久久久毛片| 97久久香蕉国产线看观看| 久久综合欧美成人| 欧美亚洲国产精品久久| 久久综合九色综合网站| 国产一区二区三精品久久久无广告 | 亚洲天堂久久精品| 久久久久久久久久免免费精品 | 国产精品久久久久9999高清| 国产精品va久久久久久久| 思思久久好好热精品国产| 久久综合九色综合久99| 国产色综合久久无码有码| 久久久久国产一级毛片高清版| 久久精品综合网| 国产农村妇女毛片精品久久| 久久亚洲中文字幕精品有坂深雪| 日本久久中文字幕| 国产精品成人99久久久久| 久久亚洲精品人成综合网| 国内精品综合久久久40p| 久久久受www免费人成| 久久亚洲精品视频| 99久久精品影院老鸭窝| 久久亚洲AV成人出白浆无码国产| 亚洲精品乱码久久久久久蜜桃| 国产福利电影一区二区三区久久久久成人精品综合 | 久久久久久夜精品精品免费啦| 亚洲国产精品成人久久蜜臀 | 久久国产免费观看精品| 亚洲AV日韩精品久久久久| 久久亚洲中文字幕精品一区| 色妞色综合久久夜夜| 久久人妻无码中文字幕| 久久久久久久综合狠狠综合|