下层到上层的边不用建 从上层到下层就已经代表了做了一次选择 如果还能回到上层的话会出问题的
因为可以免费 k 次，所以我们要建 k+1 层图
在 k+1 层图上我们已经不能再往下了，即免费操作已用完
for(int i=1,x,y,z;i<=p;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z); //本层建边
for(int j=1,z1=0;j<=k;j++)//z1是前k条边可以跑的边权
{
add(x+(j-1)*n,y+j*n,z1); //第j层和第j+1层间的建边 第j层的y到第j层的y+1
add(y+(j-1)*n,x+j*n,z1);//第j层x 到 第j+1层的y
add(x+j*n,y+j*n,z);
add(y+j*n,x+j*n,z); //第j+1层建边
}
}
//求答案法一 每一层的终点向下一层的终点连边保证第k层的终点就是答案
for(int i=1,z=0;i<=k;i++)
add(i*n,(i+1)*n,z);//防止可以免费的边大于1-n的路径这种情况 这样保证
res = dis[(k+1)*n];
//求答案法二 的时候 第一层到第k+1层
for(int i=0,i<=k,i++){
an=min(an,dis[t+i*n]);//k次操作内的最短路
}
求第k+1条贵的长度https://www.acwing.com/problem/content/description/342/
现在我们要这么更新：
z=max(edge,dis[x]); //edge是当前边权值
if ( dis[y] > z ) dis[y] = z;