迷宫

【题目描述】

破了魔法阵后，亮亮进入了一座迷宫。这座迷宫叫做“梦境迷宫”，亮亮只有走出这座迷宫，才能从睡梦中醒来。

梦境迷宫可以用无向图来表示。它共有$n$个点和$m$条双向道路，每条道路都有边权，表示通过这条道路所需的时间，且每条道路可以多次经过。亮亮位于一号点，而出口则是$n$号点。原本，亮亮该找到一条最短路，快速冲出迷宫，然而，梦境迷宫的特殊之处在于，如果沿着最短路到达出口，亮亮就永远陷入梦境。因此，亮亮必须寻找一条次短路。次短路的长度须严格大于最短路（可以有多条）的长度，同时又不大于所有除最短路外的道路的长度。

你的任务，就是编写一个程序，帮助亮亮找到通向出口的次短路。

【输入格式】

第一行有两个整数$n、m$，表示迷宫内共有$n$个点，$m$条边。

接下来$m$行，每行三个整数$x、y、z$，表示结点$x$和$y$之间连有一条边权为$z$的无向边。

【输出格式】

一个整数，表示次短路的长度。

【样例输入】

4 4 1 2 2 2 4 4 2 3 3 3 4 4

【样例输出】

9

【样例解释】

最短路：$1->2->4$ (长度为$2+4=6$)

次短路：$1->2->3->4$(长度为$2+3+4=9$)

【数据规模】

对于$100\%$的数据，$1<=n<=5000，1<=m<=100,000$。

对于$100\%$的数据，$1<=z<=5000$，$z$ 表示无向边的边长。

---

就，很快乐地打完了这题。

先从头做一遍$spfa$，再从后往前做一遍$spfa$。枚举每一条边，计算从头到入点的最短路加上从出点到尾（即从尾到出点）的最短路加上当前边的权值，记录大于最短路的最小值。

愉快$over$。

---

当然，传统次短路做法不是酱紫的。大家可以自行搜索，传统做法可做出从$1$号节点到每一个点的次短路。

官方题解用的是$dfs$加剪枝：

算法：题目要求次短路，我们可以先用$Dijkstra$算法求出最短路。设最短路长为$s1$,与结点$n$相连的最短边的长度为$c$，设$s2=s1+2\ast c$, 则$s2$就是次短路长度的上界。接下来我们只要进行$DFS$深搜即可，在搜索过程中利用上界$s2$进行剪枝，并不断更新$s2$，就可以在题目规定的时间内得到结果。

---

代码如下：

#include<bits/stdc++.h> #define N 5000+10 #define M 100000+10 using namespace std; int n,m; int d1[N],d2[N],vis[N]; vector<int>v[N]; vector<int>val[N]; struct node{ int x,y,z; }e[N]; int minn,ans=0x3f3f3f3f; void spfa1(){ queue<int>q; memset(vis,0,sizeof vis); memset(d1,0x3f,sizeof d1); q.push(1),d1[1]=0,vis[1]=1; while(q.size()){ int x=q.front();q.pop();vis[x]=0; for(int i=0;i<v[x].size();i++){ int y=v[x][i],z=val[x][i]; if(d1[y]>d1[x]+z){ d1[y]=d1[x]+z; if(!vis[y])q.push(y); vis[y]=1; } } } } void spfa2(){ queue<int>q; memset(vis,0,sizeof vis); memset(d2,0x3f,sizeof d2); q.push(n),d2[n]=0,vis[n]=1; while(q.size()){ int x=q.front();q.pop();vis[x]=0; for(int i=0;i<v[x].size();i++){ int y=v[x][i],z=val[x][i]; if(d2[y]>d2[x]+z){ d2[y]=d2[x]+z; if(!vis[y])q.push(y); vis[y]=1; } } } } void work(){ for(int i=1;i<=m;i++){ int x=e[i].x,y=e[i].y,z=e[i].z; int t1=d1[x]+d2[y]+z,t2=d1[y]+d2[x]+z; if(t1>minn&&t1<ans)ans=t1; if(t2>minn&&t2<ans)ans=t2; } } int main(){ //freopen("maze.in","r",stdin); //freopen("maze.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); e[i].x=x,e[i].y=y,e[i].z=z; v[x].push_back(y); val[x].push_back(z); v[y].push_back(x); val[y].push_back(z); } spfa1(); spfa2(); minn=d1[n]; work(); printf("%d",ans); return 0; }