次短路

poj-3255

题目：
Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.

The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1..N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.

The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).

input:
Line 1: Two space-separated integers: N and R
Lines 2.. R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)

Output:
Line 1: The length of the second shortest path between node 1 and node N

Sample input:
4 4
1 2 100
2 4 200
2 3 250
3 4 100

Sample output:
450

题目大意：给出点以及点之间的距离，求出点1和点n之间次短路的距离。

分析：此题是次短路的模板题，要求此短路只需用dij或sfa在跑出最短路径之后加上一个判断此段路径的条件有语句即可。开两个数组，一个储存最短路径，一个储存次短路径。注意：对于有的点可能没有次短路径，因而对于没有次短路径的数组元素，在代码中的体现为无穷大,具体实现实现见代码。

#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=100010;
int n,m,u,v,w;
int dis1[maxn],dis2[maxn];
struct P
{
int to,cost;
bool operator <(const P &a) const
{
    return cost>a.cost;
    }    
};
vector<P> edge[maxn];
void Dijkstra()
{
    priority_queue<P> qu;
    fill(dis1,dis1+n+1,INF);
    fill(dis2,dis2+n+1,INF);
    dis1[1]=0;
    qu.push(P{1,0});
    while(!qu.empty())
    {
        P x=qu.top();
        qu.pop();
        int v=x.to,d=x.cost;
        if(d>dis2[v])//此处判断类似于vis数组的作用，取出来的值如果是比次小值还大那么肯定是已经使用过，或没用的值。
        {
            continue;
        }
        for(int i=0;i<edge[v].size();i++)
        {
            P y=edge[v][i];
            int d2=y.cost+d;
            if(dis1[y.to]>d2)
            {
                dis1[y.to]=d2;
                qu.push(P{y.to,dis1[y.to]});
            }
            if(dis1[y.to]<d2&&dis2[y.to]>d2)//次短路的值在小于最短路的前提下，使用与求最短路相同的方法进行计算。
            {
                dis2[y.to]=d2;
                qu.push(P{y.to,dis2[y.to]});
            }
        }
    }
}




int main()
{
    while(cin>>n>>m)
    {
        for(int i=0;i<=n;i++)
        {
            edge[i].clear();
        }
        for(int i=1;i<=m;i++)
        {
            cin>>u>>v>>w;
            edge[u].push_back(P{v,w});
            edge[v].push_back(P{u,w});
        }
        Dijkstra();
        cout<<dis2[n]<<endl;
    }
    return 0;
}