首先数据貌似很水

大体思路为找到最短路上每一条边,然后枚举每条边不能走.

发现会被样例2卡飞,于是再找到在最短路上的点连出的最短的一条边额外走两遍

然后过了...(理论来说是 $O(nmlogm)$ 的复杂度,加了点小优化(唐杰斯特拉))

然而这个思路的正确性是否能证明/证伪,求各位大佬解答

以下是代码和一些手造的数据

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k;
int h[5145],e[214514],ne[214514],idx;
ll w[214514],d[5145];
int st[5145],op[5145];
ll ans=1e18;
ll gen,dgl,minn=1e18;
int cnt;
int pre[5145],fg=1,res[5145];
map<pair<int,int>,int> un;
priority_queue<pair<int,int> >q;

inline void add(int a,int b,int c)
{
	ne[idx]=h[a];
	e[idx]=b;
	w[idx]=c;
	h[a]=idx;
	idx++;
}

inline void dijk()
{
	memset(d,0x3f,sizeof d);
	//cout<<d[0];
	memset(st,0,sizeof st);
	d[1]=0;
	q.push(make_pair(0,1));
	
	while(q.size())
	{
		int x=q.top().second;
		if(x==n)
		  break;
		q.pop();
		if(st[x])
		  continue ;
		st[x]=1;  
		for(int i=h[x];~i;i=ne[i])
		{
			int y=e[i];
			if((op[y]>=k||y==n)&&d[y]>d[x]+w[i])
			{
				d[y]=d[x]+w[i];
				pre[y]=i;
				q.push(make_pair(-d[y],y));
			}
		}
	}
	while(q.size())
	  q.pop();
}

int main()
{
	
	memset(h,-1,sizeof h);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		if(a>b)
		  swap(a,b);
		if(un[make_pair(a,b)]==0)
		{
			un[make_pair(a,b)]=1;
			op[a]++;
		  op[b]++;
		}
		add(a,b,c);
		add(b,a,c);
	}
	//pre[1]=-1;
	dijk();
	dgl=d[n];
	//cout<<ans;
	if(dgl>=1e15)
	{
		cout<<-1;
		return 0;
	}
	else
	{
		for(int i=h[1];~i;i=ne[i])
		  minn=min(minn,w[i]);
		for(int i=n;i!=1;i=e[i])
		{
			for(int j=h[i];~j;j=ne[j])
			  minn=min(minn,w[j]);
			i=pre[i]^1;//cout<<i<<' ';
			res[++cnt]=i;		
		}
		//
    ans=dgl+minn+minn;
		//cout<<ans<<' ';
		for(int i=1;i<=cnt;i++)
		{
			gen=w[res[i]];
			w[res[i]]=1e9;
			w[res[i]^1]=1e9;
			dijk();
			w[res[i]]=gen;
			w[res[i]^1]=gen;
			if(d[n]!=dgl)
			  ans=min(ans,d[n]);
		}
	}  
	/*if(ans>=1e15)
	  cout<<-1;
	else*/
	cout<<ans;
	return 0;
}
/*
4 4 3
2 1 100
2 4 200
2 3 250
3 4 100
*/
/*
4 3 1
1 2 5000
2 4 5000
2 3 100
*/
/*
4 4 1
1 2 100
2 4 200
2 3 250
3 4 100
*/
/*
4 4 1
1 2 5000
2 4 5000
2 3 100
1 4 10010
*/
/*
4 4 1
1 2 5000
2 4 5000
1 3 1000
3 4 9000
*/
/*
4 3 1
1 2 11
2 3 45
3 1 14
*/
/*
3 2 1
1 3 114514
1 2 1
*/