Not The Best 严格第二短路 A*第k短路或者次短路算法

Robin has moved to a small village and sometimes enjoys returning to visit one of his best friends. He does not want to get to his old home too quickly, because he likes the scenery along the way. He has decided to take the second-shortest rather than the shortest path. He knows there must be some second-shortest path.

The countryside consists of R bidirectional roads, each linking two of the N intersections, conveniently numbered from 1 to N. Robin starts at intersection 1, and his 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

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case contains two integers N (1 ≤ N ≤ 5000) and R (1 ≤ R ≤ 105). Each of the next R lines contains three space-separated integers: u, v and w that describe a road that connects intersections u and v and has length w (1 ≤ w ≤ 5000).

Output

For each case, print the case number and the second best shortest path as described above.

Sample Input

2

3 3

1 2 100

2 3 200

1 3 50

4 4

1 2 100

2 4 200

2 3 250

3 4 100

Sample Output

Case 1: 150

Case 2: 450

题目大意:问1-n的严格的第二短路是多少

题目思路:

两种方法:A*搜第k短路或者 spfa跑严格次短路

A*需要注意的事项,因为 为严格次短路所以我们要记录一下 上一个次小值是多少,不同即可.

次短路需要注意的事项,当不满足第一个时 第二个还需要加一个 条件才能成为次短路,dis[e]>u.w+edge[i].w即可

具体看代码:

A*:54 ms

#include <bits/stdc++.h>
#include<stdio.h>
#include<vector>
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
const int mod=998244353;
const int maxn=2e5+5;
const ll INF=100000000000005;
using namespace std;
ll n,m;
ll cnt=0,cnt1=0;
int head[maxn];
ll dis[maxn];
bool vis[maxn];
struct edg{
    int e,next;
    ll w;
}edge[maxn];
struct node
{
    ll id,g;
    friend bool operator<(node a,node b)
    {
        return a.g+dis[a.id]>b.g+dis[b.id];
    }
};
void restart()
{
    memset(head,-1,sizeof(head));
    cnt=0;
    cnt1=0;
}
void addedge1(int u,int v,ll w)//双向最短路无所谓反向,单向最短路需要反向存图
{
    edge[cnt]=edg{v,head[u],w};
    head[u]=cnt++;
    edge[cnt]=edg{u,head[v],w};
    head[v]=cnt++;
}
void spfa()
{
    for(int i=1;i<=n;i++) dis[i]=INF,vis[i]=false;
    queue<int>q;
    dis[n]=0;vis[n]=true;q.push(n);
    while(!q.empty())
    {
        int u=q.front();q.pop();vis[u]=false;
        for(int i=head[u];~i;i=edge[i].next)
        {
            int e=edge[i].e;
            if(dis[e]>dis[u]+edge[i].w)
            {
                dis[e]=dis[u]+edge[i].w;
                if(!vis[e])
                {
                    vis[e]=true;
                    q.push(e);
                }
            }
        }
    }
}
ll A_start()
{
    int cot=0;
    ll pre=-1;
    priority_queue<node>q;
    q.push(node{1,0});
    while(!q.empty())
    {
        node u=q.top();q.pop();
        if(u.id==n)
        {
            if(u.g!=pre) {cot++;pre=u.g;}
            if(cot==2) return u.g;
        }
        for(int i=head[u.id];~i;i=edge[i].next)
        {
            int e=edge[i].e;
            q.push(node{e,u.g+edge[i].w});
        }
    }
}
int main()
{
    int cas=0;
    int T;scanf("%d",&T);
    while(T--)
    {
        restart();
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int x,y;ll z;
            scanf("%d%d%lld",&x,&y,&z);
            addedge1(x,y,z);
        }
        spfa();
        printf("Case %d: %lld\n",++cas,A_start());
    }
    return 0;
}

改进次短路:108ms

#include <bits/stdc++.h>
#include<stdio.h>
#include<vector>
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
const int mod=998244353;
const int maxn=3e5+5;
const ll INF=100000000000005;
using namespace std;
ll n,m;
ll dis[maxn],dis1[maxn];
bool vis[maxn];
int head[maxn];
ll cnt=0;
struct node{
    int e,next;
    ll w;
}edge[maxn];
struct N{
    int id;
    ll w;
};
void restart()
{
    memset(head,-1,sizeof(head));
    cnt=0;
}
void addedge(int u,int v,ll w)
{
    edge[cnt]=node{v,head[u],w};
    head[u]=cnt++;
}
void spfa()
{
    for(int i=1;i<=n;i++) dis[i]=dis1[i]=INF,vis[i]=false;
    queue<N>q;dis[1]=0;
    vis[1]=true;N s;s.w=0;s.id=1;q.push(s);
    while(!q.empty())
    {
        N u=q.front();q.pop();
        for(int i=head[u.id];~i;i=edge[i].next)
        {
            int e=edge[i].e;
            if(dis[e]>u.w+edge[i].w)
            {
                dis1[e]=dis[e];
                dis[e]=u.w+edge[i].w;
                q.push(N{e,dis[e]});
            }
            else if(dis1[e]>u.w+edge[i].w&&u.w+edge[i].w>dis[e])
            {
                dis1[e]=u.w+edge[i].w;
                q.push(N{e,dis1[e]});
            }
        }
    }
}
int main()
{
    int cas=0;
    int T;scanf("%d",&T);
    while(T--)
    {
        restart();
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int x,y;ll z;
            scanf("%d%d%lld",&x,&y,&z);
            addedge(x,y,z);
            addedge(y,x,z);
        }
        spfa();
        printf("Case %d: %lld\n",++cas,dis1[n]);
    }
    return 0;
}

也做了一个比较:即A*比一般搜索速度要快