題意

這題給你一個無向圖,讓你求出次短路(比最短路長,比其他路短).

思維

這裏要注意到題目是人類出的,也是給人類做的,更何況這只是一道藍題,所以極大概率不是讓你發明新算法.因此這裏最有可能是最短路的變形題.我們發現次短路與最短路是有關係的,因為構成一個次短路只有兩種可能: 

1.固定一條邊,求出起點和終點分別到端點的最短路徑,這種路徑可能是次短路.注意判定是否你直接找到最短路了.

2.最短路的一條邊被重複走了.為什麼不是多條邊被重複走?因為這樣就比只重複一條邊的長了,不是次短路.

兩種枚舉即可.

算法

這裏求最短路dijikstra SPFA都可以,作者用的是堆優化的dijikstra,因為某個算法已經死了,如果這是考場且沒有負權邊一定用dijikstra.

實現

dis數組開兩個(或者開一個二維的),分別存從起點和終點跑的最短路,這樣思路中的兩種枚舉方式都可以簡單實現.要注意,第一種方法中枚舉不要出現走重的情況,因為這種情況絕對不是次短路.

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=5e3+10, M=1e5+10;
ll n,m,dis[N][2],mi,ans=(1e12),sl=(1e12);
bool f[N];
struct node{
	ll u,d;
	bool operator < (const node &u) const{
		return u.d<d;
	}
};
vector<node>v[N];
void dij(int s, int x){
	priority_queue<node>q;
	for(int i=1;i<=n;i++) dis[i][x]=(1e12), f[i]=0;
	dis[s][x]=0, q.push({s,0});
	while(q.size()){
		node t=q.top();
		q.pop();
		if(f[t.u]) continue;
		else f[t.u]=1;
		for(int i=0;i<v[t.u].size();i++){
			int u=v[t.u][i].u, g=v[t.u][i].d;
			if(dis[u][x]>dis[t.u][x]+g){
				dis[u][x]=dis[t.u][x]+g, q.push({u,dis[u][x]});
			}
		}
	}
}
struct Edge{
	int u,v,w;
}t[M];
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>t[i].u>>t[i].v>>t[i].w;
		v[t[i].u].pb({t[i].v,t[i].w});
		v[t[i].v].pb({t[i].u,t[i].w});
	}
	dij(1,0), dij(n,1), mi=dis[n][0];
	for(int i=1;i<=m;i++){
		ll u=t[i].u, v=t[i].v, w=t[i].w;
		if(dis[u][0]+dis[v][1]>dis[u][1]+dis[v][0]) swap(u,v);
		ll s=dis[u][0]+dis[v][1]+w;
		if(s==mi) continue;
		ans=min(ans,s);
	}
	for(int i=1;i<=m;i++){
		ll u=t[i].u, v=t[i].v, w=t[i].w;
		if(dis[u][0]+dis[v][1]>dis[u][1]+dis[v][0]) swap(u,v);
		ll s=dis[u][0]+dis[v][1]+w;
		if(s!=mi) continue;
		sl=min(sl,w);		
	}ans=min(ans,mi+sl*2);
	cout<<ans;
	return 0;
}

這裏兩個swap可能匪夷所思,想象一根木棒兩端固定在兩個端點(起點和終點),很顯然有兩種擺法,一種擺法非常奇怪,繩子會長很多,因為這個擺法是從一條直線轉了180度.這裏就是如此.其他大家儘量理解.