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

            poj 3255 Roadblocks 次短路

               這個題是求次短路。有個不錯的解法,是根據一個結論,替換調最短路里面的一條邊肯定能得到次短路。
               那么,只要枚舉所有邊就可以了。比如,假設開始點為s,目標點是d,設最短路為dis(s,d)。對于邊(u,v),
            dis(s, u) + w(u, v) + dis(v, d) 大于dis(s, d),則該路徑就可能是次短路。求出最小的大于dis(s,d)的值就可以了。
               方式是從s開始和從d開始進行2次單源多終點最短路徑算法。然后枚舉邊即可。
               
               該算法可以這樣理解。因為替換最短路徑里面的邊,路徑的長度只會變大或者不變。如果存在讓更短路徑變小的邊,
            這本身就與最短路徑是矛盾的。所以替換2條或者更多的邊只會讓路徑變得更大。因此,只需考慮替換一條邊的情況
            即可。

               代碼如下:
            #include <stdio.h>
            #include <string.h>
            #include <algorithm>
            #include <queue>
            #include <vector>
            using namespace std;

            const int MAX_N = 5000 + 10;
            struct Edge
            {
                int nE;
                int nDis;
                Edge(int e, int d):nE(e), nDis(d) {}
            };
            vector<Edge> graph[MAX_N];
            bool bVisit[MAX_N];
            int nSDis[MAX_N];
            int nEDis[MAX_N];

            struct Node
            {
                int nN;
                int nDis;

                bool operator < (const Node& node) const
                {
                    return nDis > node.nDis;
                }
            };

            int ShortestPath(int nS, int nE, int* nDis, int nN)
            {
                priority_queue<Node> pq;
                memset(bVisit, falsesizeof(bVisit));
                for (int i = 1; i <= nN; i++)
                {
                    nDis[i] = 0x7fffffff;
                }
                nDis[nS] = 0;
                Node head;
                head.nDis = 0, head.nN = nS;
                pq.push(head);

                while (pq.empty() == false)
                {
                    Node head = pq.top();
                    pq.pop();
                    int nU = head.nN;
                    if (bVisit[nU]) continue;
                    bVisit[nU] = true;

                    for (int i = 0; i < graph[nU].size(); ++i)
                    {
                        int nV = graph[nU][i].nE;
                        int nLen = head.nDis + graph[nU][i].nDis;
                        if (nLen < nDis[nV])
                        {
                            nDis[nV] = nLen;
                            Node node;
                            node.nDis = nLen;
                            node.nN = nV;
                            pq.push(node);
                        }
                    }
                }
                
                return nDis[nE];
            }

            int Second(int nS, int nE, int nN)
            {
                int nShortest = ShortestPath(nS, nE, nSDis, nN);
                ShortestPath(nE, nS, nEDis, nN);

                int nAns = 0x7fffffff;

                for (int i = 1; i <= nN; ++i)
                {
                    for (int j = 0; j < graph[i].size(); ++j)
                    {
                        int nU = i;
                        int nV = graph[i][j].nE;
                        int nLen = nSDis[i] + graph[i][j].nDis + nEDis[nV];
                        if (nLen != nShortest)
                        {
                            nAns = min(nAns, nLen);
                        }
                    }
                }

                return nAns;
            }

            int main()
            {
                int nN, nR;
                int nA, nB, nD;

                while (scanf("%d%d", &nN, &nR) == 2)
                {
                    for (int i = 1; i <= nN; ++i)
                    {
                        graph[i].clear();
                    }

                    while (nR--)
                    {
                        scanf("%d%d%d", &nA, &nB, &nD);
                        graph[nA].push_back(Edge(nB, nD));
                        graph[nB].push_back(Edge(nA, nD));
                    }
                    printf("%d\n", Second(1, nN, nN));
                }

                return 0;
            }

            posted on 2012-09-03 22:39 yx 閱讀(1507) 評論(0)  編輯 收藏 引用 所屬分類: 圖論

            <2013年6月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            30123456

            導航

            統計

            公告

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            me

            好友

            同學

            網友

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            麻豆亚洲AV永久无码精品久久| 成人国内精品久久久久影院VR| 欧美日韩精品久久久久 | 久久人人爽人人人人片av| 国产亚洲美女精品久久久2020| www.久久热.com| 久久久久亚洲精品天堂久久久久久| 久久久一本精品99久久精品88| 精品国产乱码久久久久久郑州公司| 久久亚洲精品中文字幕三区| 欧美日韩精品久久久免费观看| 久久精品国产亚洲av麻豆色欲| 久久996热精品xxxx| 99久久超碰中文字幕伊人| 四虎影视久久久免费| 97久久天天综合色天天综合色hd| 久久影院午夜理论片无码| 91精品国产高清久久久久久国产嫩草| 伊人久久一区二区三区无码| 久久国产精品免费| 久久97精品久久久久久久不卡| 一本一道久久a久久精品综合 | 精品国产福利久久久| 色婷婷综合久久久久中文字幕| 久久精品国产亚洲精品2020 | 亚洲国产精品无码久久一线| 久久久久久国产精品美女| 91精品国产91热久久久久福利| 久久精品国产亚洲av影院| 亚洲精品国精品久久99热一| 久久午夜福利无码1000合集| 国内精品伊人久久久久网站| 日韩一区二区久久久久久| 99麻豆久久久国产精品免费| 久久精品国产亚洲av水果派| 亚洲AV乱码久久精品蜜桃| 狠狠色丁香久久婷婷综合图片| 色播久久人人爽人人爽人人片AV| 久久久久一级精品亚洲国产成人综合AV区 | 色综合久久中文字幕综合网| 久久av免费天堂小草播放|