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次單源多終點最短路徑算法。然後枚舉邊即可。
  
   該算法可以這樣理解。因為替換最短路徑裡面的邊，路徑的長度只會變大或者不變。

   代碼如下：
#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, false, sizeof(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));
        }   www.2cto.com
        printf("%d\n", Second(1, nN, nN));
    }

    return 0;
}