这道题本蒟蒻用线段树和 Dij 等算法就轻松过了，（这个方法是从桥那道题的题解学来的）

由于之前只AC过1道黑题，所以我偷偷高兴了好久

虽然我过了， 但是我在其他讨论里找到一组数据，

发现我竟然过不了这组数据，

先来给大家看一下我的代码：

（dalao 们不喜勿喷）

#include <queue>
#include <cstdio>
#include <iostream>
#define gc getchar
int min(int x,int y){return x<y?x:y;}
int rd(){
	int x=0;char c=gc();
	while(c<'0'||c>'9')c=gc();
	while(c>='0'&&c<='9')x=x*10+(c^48),c=gc();
	return x;
}
const int N = 100003;
const int INF = 0x7fffffff;
int B,n,m,T,u,v,w,cnt;
int h2[N],h[N],d1[N],dn[N],res[N],L[N],R[N],st[N],id[N],t[N<<2];
bool I[N<<2];
struct E{
	int nxt,v,w;
}e[N<<1],e2[N<<1];
struct P{
	int p,w;
};
bool operator<(P a,P b){
	return a.w>b.w;
}
std::priority_queue<P>q;
std::queue<int>Q;
void add(){
	e[++cnt]=(E){h[u],v,w},h[u]=cnt;
	e2[cnt]=(E){h2[v],u,w},h2[v]=cnt;
}
void Dijkstra_1()
{
	for(int i=2;i<=n;++i)d1[i]=INF;
	q.push((P){1,0});
	while(!q.empty()){
		u=q.top().p,w=q.top().w,q.pop();
		if(w>d1[u])continue;
		for(int i=h[u];i;i=e[i].nxt){
			v=e[i].v;
			if(d1[v]>e[i].w+w)d1[v]=e[i].w+w,q.push((P){v,d1[v]});
		}
	}
}
void Dijkstra_2()
{
	for(int i=1;i<n;++i)dn[i]=INF;
	q.push((P){n,0});
	while(!q.empty()){
		u=q.top().p,w=q.top().w,q.pop();
		if(w>dn[u])continue;
		for(int i=h2[u];i;i=e2[i].nxt){
			v=e2[i].v;
			if(dn[v]>e2[i].w+w)dn[v]=e2[i].w+w,q.push((P){v,dn[v]});
		}
	}
}
void bfs(int x,int*d,int*f,E*ee,int*hh)
{
	Q.push(st[x]),f[st[x]]=x;
	while(!Q.empty()){
		u=Q.front(),Q.pop();
		for(int i=hh[u];i;i=ee[i].nxt){
			v=ee[i].v;
			if(!id[v]&&!f[v])
				if(d[u]+ee[i].w==d[v])
					f[v]=x,Q.push(v);
		}
	}
}
#define ls (p<<1)
#define rs (p<<1|1)
void mkt(int p,int l,int r){
	t[p]=INF;
	if(l==r)return;
	int mid=(l+r)>>1;
	mkt(ls,l,mid),mkt(rs,mid+1,r);
}
void modify(int p,int l,int r,int nl,int nr,int k){
	if(nl<=l&&r<=nr){t[p]=min(t[p],k);return;}
	int mid=(l+r)>>1;
	if(nl<=mid)modify(ls,l,mid,nl,nr,k);
	if(nr>mid)modify(rs,mid+1,r,nl,nr,k);
}
#undef ls
#undef rs
void down(int p,int l,int r){
	if(l==r){res[l]=t[p];return;}
	int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;
	t[ls]=min(t[ls],t[p]);
	t[rs]=min(t[rs],t[p]);
	down(ls,l,mid),down(rs,mid+1,r);
}
int main(void)
{
	n=rd(),m=rd(),B=rd();
	for(int i=1;i<=m;++i){
		u = rd(),v = rd(),w = rd();
		add();
	}
	while(B--)rd();
	Dijkstra_1();
	Dijkstra_2();
	u=1;
	while(u<n)
	{
		st[++T]=u;id[u]=T;
		for(int i=h[u];i;i=e[i].nxt){
			v=e[i].v;
			if(dn[u]==dn[v]+e[i].w){
				I[i]=1,u=v;break;
			}
		}
	}st[++T]=n;id[n]=T;
	for(int i=1;i<=T;++i)bfs(i,d1,L,e,h),bfs(i,dn,R,e2,h2);
	--T,mkt(1,1,T);
	for(int i=1;i<=cnt;++i)
		if(!I[i]){
			v=e[i].v;u=e2[i].v;
			if(L[u]<R[v])modify(1,1,T,L[u],R[v]-1,d1[u]+e[i].w+dn[v]);
		}
	down(1,1,T);
	for(int i=1;i<=T;++i)
	if(res[i]==INF)std::cout<<-1<<'\n';
	else std::cout<<res[i]<<'\n';
}

用我的代码，

这组数据是过不去的。

5 7 3
1 2 1
2 3 1
3 5 1
1 4 10
4 2 1
3 4 1
4 5 10
1 2 3

正确输出：

13
20
13

欢迎大家一起讨论。