注意此时的大于和小于是指我们对最短路上的点编号后的结果

3.解法实现

说了这么多性质，到底如何实现呢？？？

显然我们不可能对每一条边断开后单独求解

那我们就考虑是不是答案有传递性，相互之间的贡献，或者任何共同性可以减少复杂度的

那我们的性质就要派上用场了 （废话

我们发现，我们的绕路都是从一个地方跳出来，然后再回去

从$1-n$的顺序遍历，如果前面的路径也绕开了这条边，我们是不是就可以使用呢？

显然，之前的答案对于现在是有贡献的，但是不一定是最优的

所以我们是不是还要从这条断边的起点SPFA一次，获得这个点对答案（也就是绕开路径）的贡献

那答案是否有有限的贡献范围呢？

显然，如果这一条远路没有绕开断边，对后面的答案都没有贡献了

所以绕远路的终点，也就是回到最短路上的点，需要比现在的断边的终点大

然后我们又发现，断边的枚举是递增的

每次插入一个比现在大的点和权值，然后寻找最小的权值且满足要求

动态维护一个最小值，支持删除插入，时间复杂度在$O(log\space n)$左右，我们就可以突发奇想，想到小根堆！

接下来整理解法

• 存图+对最短路上的点顺序编号+求到终点的最短路值（后面会用到）

• 顺序枚举最短路上的点

• 对于当前的点，SPFA寻找后继节点

由于这里找到最短路上的点后需要快速得到到终点的长度，并插入堆

所以预处理一个到终点的最短路值，同时减少没有必要的尝试，减少时间

• 从堆顶取出元素，如果路径没有绕过断边，踢出堆

• 如果堆顶无元素，输出-1，否则输出解

• 更新到当前点的最短路（之前走的都是绕远路来的）

• 如果这一条边的终点是n，结束

其实就是这幅图啦

4.时间复杂度简析

蒟蒻只会简单分析，有错请指正

设最短路上有$n_1$个点，不在最短路上有$n_2$个点

枚举断边$O(n_1)$

每一个断边最坏需要$O(n_2\space m)$

那复杂度就需要$O(n_1\space n_2\space m)$

还有一个堆的复杂度$O(log n_1)$

貌似很大，但是每一次拓展，堆理论的大小都会减小，SPFA的拓展也越来越有限，而且这理论上是一个稀疏图

综上，复杂度为$O(\text{玄学能过})$

只要常数好，就卡得过

所以这是一段瞎扯

5.代码

还是这个最重要

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read()//蒟蒻不太会快读（雾）
{
	int ans=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') 
	{
		if(ch=='-') f*=-1;
		ch=getchar();
	}
	ans=ch-'0';
	ch=getchar();
	while(ch>='0'&&ch<='9') ans*=10,ans+=ch-'0',ch=getchar();
	return ans;
}
const int N=2e5+5;
int n,m,l;
int num[N],rode[N],dis1[N],disn[N],along[N];
struct edge{
	int u,v,nex,w;
}edge[N<<1];
struct node{
	int u,dis;
	node(int uu,int diss){u=uu,dis=diss;}
	bool operator <(const node &x)const{
		return dis>x.dis;//注意符号，我们要小根堆
	}
};
priority_queue<node>s;
int head[N],top=0;
void add(int u,int v,int w)//日常加边
{
	edge[++top].v=v;
	edge[top].u=u;
	edge[top].w=w;
	edge[top].nex=head[u];
	head[u]=top;
}
bool vis[N],viss[N<<1];
void SPFA(int S)//日常SPFA
{
	queue<int>q;
	for(int i=1;i<=n;i++) vis[i]=0;
	q.push(S);
	vis[S]=1; 
	while(!q.empty())
	{
		int u=q.front(); q.pop(); 
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].nex)
		{
			int v=edge[i].v;
			if(!viss[i]&&dis1[v]>dis1[u]+edge[i].w)//不能过原最短路上的边，保证只走远路
			{
				dis1[v]=dis1[u]+edge[i].w;
				if(num[v]) s.push(node(num[v],dis1[v]+disn[num[v]]));//跑回最短路就插入堆
				else if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
int main()
{
	n=read(),m=read(),l=read();
	for(int i=1,u,v,w;i<=m;i++) u=read(),v=read(),w=read(),add(u,v,w);
	for(int i=1;i<=l;i++)//标记最短路
	{
		rode[i]=read();
		along[i+1]=edge[rode[i]].v;//记录点
		num[along[i+1]]=i+1;//对最短路上的点编号
		viss[rode[i]]=1;//记录最短路的边
	} 
	for(int i=l;i;i--) disn[i]=disn[i+1]+edge[rode[i]].w;//求出到n点的最短距离
	memset(dis1,0x3f,sizeof(dis1));//到1点的最短路，服务于SPFA
	dis1[1]=0;
	along[1]=1;
	SPFA(1);
	for(int i=1;i<=l;i++)
	{
		while(!s.empty()&&s.top().u<=i) s.pop();//没有绕开断边
		printf("%d\n",s.empty()?-1:s.top().dis);//用堆求解
		dis1[edge[rode[i]].v]=dis1[edge[rode[i]].u]+edge[rode[i]].w;//更新到1点的最短路，服务于SPFA
		SPFA(edge[rode[i]].v);
	}
	return 0;//完结撒花
}

看在这么长的题解+图片上，点个赞再走嘛。