這個(gè)題是求次短路。有個(gè)不錯(cuò)的解法，是根據(jù)一個(gè)結(jié)論，替換調(diào)最短路里面的一條邊肯定能得到次短路。
那么，只要枚舉所有邊就可以了。比如，假設(shè)開(kāi)始點(diǎn)為s，目標(biāo)點(diǎn)是d，設(shè)最短路為dis(s,d)。對(duì)于邊(u,v)，
dis(s, u) + w(u, v) + dis(v, d) 大于dis(s, d)，則該路徑就可能是次短路。求出最小的大于dis(s,d)的值就可以了。
方式是從s開(kāi)始和從d開(kāi)始進(jìn)行2次單源多終點(diǎn)最短路徑算法。然后枚舉邊即可。
該算法可以這樣理解。因?yàn)樘鎿Q最短路徑里面的邊，路徑的長(zhǎng)度只會(huì)變大或者不變。如果存在讓更短路徑變小的邊，
這本身就與最短路徑是矛盾的。所以替換2條或者更多的邊只會(huì)讓路徑變得更大。因此，只需考慮替換一條邊的情況
即可。
代碼如下：
#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));
}
printf("%d\n", Second(1, nN, nN));
}
return 0;
}