题解:
次短路模板。
代码:
#include<cstdio>
#include<iostream>
using namespace std;
#define inf 1e9
#define N 100005
#define S1 dis[x]+e[i].v
#define S2 sdis[x]+e[i].v
using namespace std;
struct node {
int to,next,v;
} e[N<<];
int head[N],cnt;
void insert(int x, int y, int v) {
e[++cnt].to=y;
e[cnt].next=head[x];
e[cnt].v=v;
head[x]=cnt;
}
int n,m,dis[N],sdis[N],q[N<<];
bool inq[N];
void SPFA() {
for(int i=; i<=n; i++)dis[i]=sdis[i]=inf;
dis[]=;
q[]=inq[]=;
int l=,r=,t;
while (l<r) {
int x=q[l++];
for (int i=head[x]; i; i=e[i].next) {
t=e[i].to;
if (dis[t]>S1) {
sdis[t]=dis[t];
dis[t]=S1;
if (!inq[t])inq[t]=,q[r++]=t;
}
if (dis[t]<S1&&sdis[t]>S1) {
sdis[t]=S1;
if (!inq[t])inq[t]=,q[r++]=t;
}
if (sdis[t]>S2) {
sdis[t]=S2;
if (!inq[t])inq[t]=,q[r++]=t;
}
}
inq[x]=;
}
}
int main() {
cin>>n>>m;
for (int i=,x,y,v; i<=m; i++) {
cin>>x>>y>>v;
insert(x,y,v);
insert(y,x,v);
}
SPFA();
cout<<sdis[n];
return ;
}
spfa
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
const int MAX = ;
const int INF = 0x7fffffff;
using namespace std;
struct Edge {
int num,len;
bool operator <(const Edge &a)const {
return a.len < len;
}
}temp;
int u[MAX],v[MAX],w[MAX],dis[MAX],second[MAX],first[MAX / ],next[MAX],n,r;
void dijkstra() {
priority_queue<Edge> que;
dis[] = ;
second[] = INF;
for(int i = ; i < n; i++) dis[i] = second[i] = INF;
temp.len = temp.num = ;
que.push(temp);
while(!que.empty()) {
Edge head = que.top();
que.pop();
if(head.len > second[head.num]) continue;
int k = first[head.num];
while(k != -) {
int d = head.len + w[k];
if(dis[v[k]] > d) {
swap(dis[v[k]], d);
temp.len = dis[v[k]];
temp.num = v[k];
que.push(temp);
}
if(dis[v[k]] < d && second[v[k]] > d) {
second[v[k]] = d;
temp.len = second[v[k]];
temp.num = v[k];
que.push(temp);
}
k = next[k];
}
}
}
int main() {
scanf("%d%d",&n,&r);
memset(first, -, sizeof(first));
for(int i = ; i < r; i++) {
scanf("%d%d%d",&u[i],&v[i],&w[i]);
u[i]--,v[i]--,next[i] = first[u[i]],first[u[i]] = i,u[i + r] = v[i];
v[i + r] = u[i],w[i + r] = w[i],next[i + r] = first[u[i + r]],first[u[i + r]] = i + r;
}
dijkstra();
printf("%d",second[n-]);
return ;
}
dijkstra
一世安宁