题意：
n个点，m条边，问从1走到n的最短路，其中有K次机会可以让一条路的权值变成0。
1≤N≤10000;1≤M≤500000;1≤K≤20
题解：
拆点，一个点拆成K个，分别表示到了这个点时还有多少次机会。
（x,k)-->(y,k-1),cost=0 或 (x,k)-->(y,k),cost=a[i].d;
这题数据比较大， 需要很多优化。（应该只是蒟蒻我才需要这么多优化。。）
1.不用spfa（时间复杂度不稳定），用dijkstra+优先队列优化
2.拆点不拆边。g[i]表示i这个点是由谁拆分出来的，id[i]表示i这个点表示还能用几次，st[i]表示i拆分出来的点的编号从什么开始，图就按照原图建立，比如(x,k)-->(y,k-1)就可以直接找到st[x]+k -- > st[y]+k-1。
3.如果“目标点n 用完了K次机会”这个状态到1的最短路已经算出来了，那一定是最优的，其它的都不用算了。加了这句话从10s+跑到了0.6s。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std; typedef long long LL;
const int N=**,M=;//不知道为什么点要开两倍才能过。。。
const LL INF=(LL)1e15;
struct node{
int x,y,next;
LL d;
}a[*M];
int n,m,K,len,num,first[N],g[N],id[N],st[N];
LL dis[N],mn[N];
struct point{int x;LL d;};
struct cmp{
bool operator () (point &x,point &y){return x.d>y.d;}
};
priority_queue<point,vector<point>,cmp> q; LL minn(LL x,LL y){return x<y ? x:y;} void ins(int x,int y,LL d)
{
a[++len].x=x;a[len].y=y;a[len].d=d;
a[len].next=first[x];first[x]=len;
} void dijkstra()
{
int y,bk=;
point t;
for(int i=;i<=num;i++) dis[i]=-;
// for(int i=1;i<=num;i++) if(dis[i]!=-1) printf("%d g = %d id = %d dis = %lld\n",i,g[i],id[i],dis[i]); memset(mn,,sizeof(mn));
while(!q.empty()) q.pop();
for(int i=;i<=K;i++) dis[st[]+i]=; for(int i=first[];i;i=a[i].next)
{
for(int j=;j<=K;j++)
{
t.x=st[a[i].y]+j;
t.d=dis[st[]+j]+a[i].d;
if(mn[t.x]>t.d) mn[t.x]=t.d,q.push(t);//如果原来这个点已经可以被更优的所更新，那就不放到队列里面。
if(j>=)
{
t.x=st[a[i].y]+j-;
t.d=dis[st[]+j];
if(mn[t.x]>t.d) mn[t.x]=t.d,q.push(t);
}
}
}
while(!q.empty() && !bk)
{
while(!q.empty())
{
t=q.top();q.pop();
if(dis[t.x]==-)
{
dis[t.x]=t.d;
y=t.x;
if(y==st[n]) bk=;
//如果“目标点n 用完了K次机会”这个状态到1的最短路已经算出来了，那一定是最优的，其它的都不用算了。加了这句话从10s+跑到了0.6s。
break;
}
}
for(int i=first[g[y]];i;i=a[i].next)
{
t.x=st[a[i].y]+id[y];
t.d=dis[y]+a[i].d;
if(dis[t.x]==- && mn[t.x]>t.d) mn[t.x]=t.d,q.push(t);
if(id[y]>=)
{
t.x=st[a[i].y]+id[y]-;
t.d=dis[y];
if(dis[t.x]==- && mn[t.x]>t.d) mn[t.x]=t.d,q.push(t);
}
}
}
} int main()
{
// freopen("a.in","r",stdin);
freopen("revamp.in","r",stdin);
freopen("revamp.out","w",stdout);
scanf("%d%d%d",&n,&m,&K);
len=;num=;
memset(first,,sizeof(first));
for(int i=;i<=m;i++)
{
int x,y;LL d;
scanf("%d%d%lld",&x,&y,&d);
ins(x,y,d);
ins(y,x,d);
}
for(int i=;i<=n;i++)
for(int j=;j<=K;j++)
{
g[++num]=i,id[num]=j;
if(j==) st[i]=num;
} dijkstra();
// for(int i=1;i<=num;i++) if(dis[i]!=-1) printf("%d g = %d id = %d dis = %lld\n",i,g[i],id[i],dis[i]);
LL ans=INF;
for(int i=st[n];i<=st[n]+K;i++)
if(dis[i]!=-) ans=minn(ans,dis[i]);
printf("%lld\n",ans);
return ;
}