洛谷 P2865 [USACO06NOV]路障Roadblocks 题解【次短路】【最短路】
点击量：107
次短路问题有两种解决方案——
题目描述
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).
贝茜把家搬到了一个小农场，但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。 贝茜所在的乡村有R(1<=R<=100,000)条双向道路，每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1，她的朋友们居住在农场N（即贝茜每次旅行的目的地）。 贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。
输入输出格式
输入格式：
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)
输出格式：
Line 1: The length of the second shortest path between node 1 and node N
输入输出样例
输入样例#1：4 41 2 1002 4 2002 3 2503 4 100输出样例#1：450说明
Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450)
算是最短路问题的一个模板了。
我们首先会想到一种做法，就是在整条最短路上枚举所有的边，从边的一端出发，不经过这条边而到达另一端的最短路，将整条最短路减去删掉的边再加上新求的最短路，就是解。但是这个解法明显是有问题的，因为最短路不止一条，次短路也不止一条，那我们如果只找到这条最短路，答案当然是有局限性的，因此这种做法被pass掉。
介绍一种dijkstra的做法，就是dis数组储存两个信息，一是最短路，二是次短路，当最短路被更新时，让原来的最短路去更新次短路，然后将两个状态分别进队（优先队列）。而进队的状态要区分开，最短路的状态既可以更新最短路又可以更新次短路，更新次短路的前提是该次短路有更短的最短路，而直接更新最短路就是间接让最短路再更新次短路，次短路的状态只能更新次短路，因为最短路一定是被原次短路的最短路状态更新过了，再更新是没有意义的。这样用堆/优先队列维护，就可以求出源点到每个点的次短路。例如下面的图（改编自样例）
这是我们第一次松弛的状态，而我们看到3可以去松弛4，因此3把4的最短路数据顶到了次短路上。
2,3的最短路顺便把已经有最短路的1,2的次短路松弛了。
我们可以看到，这种做法使dijkstra的进队次数变多了，效率上会有些许影响，并且还有最短路和次短路的混合判断。接下来介绍更优一点的SPFA做法。
SPFA较为简单，从1号点（源点）跑一遍最短路，记录为dis[1][i]，再从汇点跑一遍最短路，记录为dis[2][i]，接着枚举每条边(u,v,w)，如果dis[1][u]+w+dis[2][v]>len(最短路长度)，更新最短次短路的长度，时间复杂度是两次SPFA，最后判断的时间复杂度只用枚举边数O(E)。
总的来说，SPFA效率较高，写起来比较方便无脑，并且适用范围比较大，所以一般情况下推荐使用SPFA。（还能处理负权边……）
Code：dijkstra
#include<cstdio>
#include<cstring>
struct node//链表
{
int n,v;
node *nxt;
node(int n,int v)
{
this->n=n;
this->v=v;
nxt=NULL;
}
node()
{
nxt=NULL;
}
};
node head[5100],*tail[5100];
struct statu//状态
{
int n,dis,k;//k存是最短路还是次短路
statu(int n,int k,int dis)
{
this->n=n;
this->k=k;
this->dis=dis;
}
statu(){}
friend bool operator >(statu a,statu b)
{
return a.dis>b.dis;
}
}h[2500000];
int tt=0;
void swap(statu &a,statu &b)//手写堆部分
{
statu c=a;
a=b;
b=c;
return;
}
void put(statu x)
{
h[++tt]=x;
int i=tt;
while(i!=1&&h[i>>1]>h[i])
{
swap(h[i],h[i>>1]);
i>>=1;
}
}
void pop()
{
h[1]=h[tt--];
int i=1;
while((i<<1)<=tt&&(h[i]>h[i<<1]||(h[i]>h[i<<1|1]&&(i<<1)!=tt)))
{
if(h[i<<1|1]>h[i<<1]||(i<<1)==tt)
{
swap(h[i<<1],h[i]);
i<<=1;
}
else
{
swap(h[i<<1|1],h[i]);
i=i<<1|1;
}
}
}
int dis[5100],dis1[5100];
bool used[2][5100];
void dijk(int n)
{
memset(used,0,sizeof(used));
memset(dis,0x3f,sizeof(dis));
memset(dis1,0x3f,sizeof(dis1));
int num=0;
dis[1]=0;
put(statu(1,0,0));
while(num<=2*n)
{
statu t=h[1];
pop();
if(used[t.k][t.n])
continue;
num++;
node *p=&head[t.n];
while(p->nxt!=NULL)
{
p=p->nxt;
//if(t.k==0&&!used[0][p->n])
if(t.k==0)
{
if(dis[p->n]>t.dis+p->v)
{
dis1[p->n]=dis[p->n];
dis[p->n]=t.dis+p->v;
put(statu(p->n,0,dis[p->n]));
put(statu(p->n,1,dis1[p->n]));
}
else if(dis1[p->n]>t.dis+p->v)
{
dis1[p->n]=t.dis+p->v;
put(statu(p->n,1,dis1[p->n]));
}
}
if(t.k==1&&!used[1][p->n])
if(dis1[p->n]>t.dis+p->v)
{
dis1[p->n]=t.dis+p->v;
put(statu(p->n,1,dis1[p->n]));
}
}
}
return;
}
int main()
{
int n,m,u,v,w;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
tail[i]=&head[i];
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
tail[u]->nxt=new node(v,w);
tail[u]=tail[u]->nxt;
tail[v]->nxt=new node(u,w);
tail[v]=tail[v]->nxt;
}
dijk(n);
printf("%d\n",dis1[n]);
return 0;
}
Code：SPFA
#include<cstdio>
#include<cstring>
#include<queue>
using std::deque;
struct edge
{
int n,v;
int nxt;
edge(int n,int v,int nxt)
{
this->n=n;
this->v=v;
this->nxt=nxt;
}
edge()
{
nxt=-1;
}
}e[210000];
int cnt=-1;
int head[5010];
void add(int from,int to,int v)
{
e[++cnt]=edge(to,v,head[from]);
head[from]=cnt;
}
int n;
int dis[3][5555];
void spfa(int s,int T)
{
bool used[5555];
memset(used,0,sizeof(used));
memset(dis[T],0x3f,sizeof(dis[T]));
deque<int> q;
q.push_back(s);
used[s]=true;
dis[T][s]=0;//额外的一维存的是到哪边的最短路
while(!q.empty())
{
int k=q.front();
q.pop_front();
used[k]=false;
for(int i=head[k];~i;i=e[i].nxt)
{
if(dis[T][e[i].n]>dis[T][k]+e[i].v)
{
dis[T][e[i].n]=dis[T][k]+e[i].v;
if(!used[e[i].n])
{
used[e[i].n]=true;
if(q.empty()||dis[T][e[i].n]<dis[T][q.front()])
q.push_front(e[i].n);
else
q.push_back(e[i].n);
}
}
}
}
return;
}
int main()
{
int m,u,v,w;
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
spfa(1,1);//两次SPFA
spfa(n,2);
int len=dis[1][n],ans=998244353;
for(int i=1;i<=n;i++)
for(int j=head[i];~j;j=e[j].nxt)
if(dis[1][i]+e[j].v+dis[2][e[j].n]>len)
ans=ans<dis[1][i]+e[j].v+dis[2][e[j].n]?ans:dis[1][i]+e[j].v+dis[2][e[j].n];
printf("%d\n",ans);
return 0;
}
说点什么