题解
记录 (dp(u,0/1)) 分别表示最短路和次短路。
考虑转移，分析 (dp(u/v,0/1)) 的对应转移关系和大小关系。
[dp(u,0)<dp(v,0)
]
[dp(u,1)<dp(v,1)
]
分三个判断转移：
- 转移 (dp(v,0))：(dp(u,0) Rightarrow dp(v,0),dp(v,0)Rightarrow dp(v,1)) 和换根 DP 记录最大值，次大值类似。
- 转移 (dp(v,1))：(dp(u,0)Rightarrow dp(v,1))，但是同时要保证 (dp(v,0)) 不是从 (dp(u,0)) 转移过来的，否则就会把 (dp(v,1)) 更新成到 (v) 的最大值。
- 转移 (dp(v,1))：(dp(u,1)Rightarrow dp(v,1))，这个就没有上一条那样的限制了。
还有一点细节，在代码里面标注出来。
代码
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f,N = 5005,M = 1e5+10;
#define ll long long
#define int signed
inline ll read()
{
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9')) ch=c,c=getchar();
while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
int n,m,k;
int head[N],ecnt=-1,oud[N];
bool vis[N],mp[N][N];
ll dis[N][2];
inline void init(){memset(head,-1,sizeof(head)),ecnt=-1;}
struct edge
{
int nxt,to,w;
}a[M<<1];
inline void add_edge(int x,int y,const int w)
{
a[++ecnt]=(edge){head[x],y,w};
head[x]=ecnt;
}
void SPFA()
{
queue<int> q;
memset(dis,0x3f,sizeof(dis));
dis[1][0]=0ll;
q.push(1);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];~i;i=a[i].nxt)
{
int v=a[i].to;
if(oud[v]<k&&v!=n&&v!=1) continue;
bool flag=0;
if(dis[v][0]>dis[u][0]+a[i].w)
{//转移1
dis[v][1]=dis[v][0];
dis[v][0]=dis[u][0]+a[i].w;
flag=1;
}
if(dis[v][1]>dis[u][0]+a[i].w&&dis[v][0]<=dis[u][0]+a[i].w)//这一句if前面不能写else
{//转移2
dis[v][1]=dis[u][0]+a[i].w;
flag=1;
}
else if(dis[v][1]>dis[u][1]+a[i].w)//这一句if前面的else可写可不写
{//转移3
dis[v][1]=dis[u][1]+a[i].w;
flag=1;
}
if(flag&&!vis[v]) q.push(v),vis[v]=1;
}
}
}
int main()
{
init();
n=read(),m=read(),k=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
add_edge(u,v,w),add_edge(v,u,w);
if(mp[u][v]) oud[u]--,oud[v]--;//判断重边，自环
mp[u][v]=mp[v][u]=1;
oud[v]++,oud[u]++;
}
SPFA();
printf("%lld
",dis[n][1]>1e18?-1:dis[n][1]);
return 0;
}