Roadblocks

直接翻译了

Descriptions

Bessie搬到了一个新的农场，有时候他会回去看他的老朋友。但是他不想很快的回去，他喜欢欣赏沿途的风景，所以他会选择次短路，因为她知道一定有一条次短路。
这个乡村有R(1<=R<=100000)条双向道路，每一条连接N(1<=N<=5000)个点中的两个。Bessie在1号节点，他的朋友家是n号节点Input第一行：两个整数N和R
接下来R行:每行包含三个整数，A，B,D，表示一条连接A与B的长度为D的路径Output输出1到n的次短路

Sample Input
4 4

1 2 100

2 4 200

2 3 250

3 4 100
Sample Output
450

Hint

两条路线：1 - > 2 - > 4（长度100 + 200 = 300）和1 - > 2 - > 3 - > 4（长度100 + 250 + 100 = 450）

题目链接

https://vjudge.net/problem/POJ-3255

求从s到t的次短路径有两种情况：1、起点s到某个顶点u的最短路+d(u,t)。2、起点到某个顶点u的次短路+d(u,t)。

所以更新路径的时候需要把最短路径和次短路径两个都记录下来。

送一组数据

答案应该是500，然而如果初始化为0则答案会输出700。因为500的结果是又1到2，在从2返回1，再到2，再到4,100+100+100+200=500得到的；如果次短边初始化为0，则次短路径不再返回源点，而是在2与4之间折返，会偏大。

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define IOS ios_base::sync_with_stdio(0); cin.tie(0)

#define Mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

#define Maxn 5000+5

#define P pair<int,int>//first最短路径second顶点编号

using namespace std;

int N,R;

struct edge

{

    int to,dis;

    edge(int to,int dis):to(to),dis(dis) {}

};

vector<edge>G[Maxn];//G[i] 从i到G[i].to的距离为dis

int d[Maxn][Maxn];//d[i][j]从i到j的最短距离

int d2[Maxn][Maxn];//d[i][j]从i到j的次短距离

void Dijk(int s)

{

    priority_queue<P,vector<P>,greater<P> >q;//按first从小到大出队

    for(int i=; i<=N; i++)//初始化s到所有地方的最短路，次短路都是inf

        d[s][i]=INF,d2[s][i]=INF;

    d[s][s]=;

    q.push(P(,s));

    while(!q.empty())

    {

        P p=q.top();

        q.pop();

        int v=p.second;//点v

        if(d2[s][v]<p.first)//大于次短路径，肯定会大于最短路径，不用管他了

            continue;

        for(int i=; i<G[v].size(); i++)

        {

            edge e=G[v][i];//枚举与v相邻的点

            int td=p.first+e.dis;//s到v的距离+v到e.to的距离

            if(d[s][e.to]>td)//s到e.to的最短路小于dt，更新d[s][e.to]

            {

                swap(d[s][e.to],td);

                q.push(P(d[s][e.to],e.to));

            }

            if(d[s][e.to]<td&&d2[s][e.to]>td)//td大于最短路，小于次短路，即td可以替换次短路

            {

                d2[s][e.to]=td;

                q.push(P(d2[s][e.to],e.to));

            }

        }

    }

}

int main()

{

    IOS;

    cin>>N>>R;

    for(int i=; i<R; i++)

    {

        int u,v,d;

        cin>>u>>v>>d;

        G[u].push_back(edge(v,d));

        G[v].push_back(edge(u,d));

    }

    Dijk();//城市1到各个城市的最短距离，次短路

    cout<<d2[][N]<<endl;

    return ;

}

巴特西

【POJ - 3255】Roadblocks（次短路 Dijkstra算法）

Roadblocks

最新文章

热门文章