@[小粉兔](/user/10703) @[yurzhang](/user/126486)
by ReTF @ 2022-08-09 11:30:16
@[ReanimateThroughFire](/user/578628)
建议补充说明可以 hack 掉哪几组题解,hack 掉什么做法,以及证明自己数据的可行性
by PassName @ 2022-08-09 11:49:10
@[单南松](/user/524911)
该hack数据可以卡掉一些没有特判 $k$ 大于路径长度(即没有把给定次数全用完)的做法。
将这份分层图代码删去带大坑注释的一行可以通过原版数据,但不能通过hack
```cpp
#include<bits/stdc++.h>
#define inf 1000100
#define pii pair<int,int>
#define mp make_pair
#define f first
#define s second
using namespace std;
vector<pii>l[inf];
bool vis[inf];int dis[inf];
int n,m,s;
struct node{
int d,p;
bool operator <( const node &x )const{return x.d<d;}
};
priority_queue<node> q;
void dijkstra(){
s=1;
memset(dis,100,sizeof(dis));
dis[s] = 0;
q.push((node){0,s});
while(!q.empty()){
node t = q.top();
q.pop();
int x = t.p;
if(vis[x])
continue;
vis[x] = 1;
for(int i=0;i<l[x].size();i++){
int y=l[x][i].f;
if(dis[y]>max(dis[x],l[x][i].s)){
dis[y]=max(dis[x],l[x][i].s);
if(!vis[y])
q.push((node){dis[y],y});
}
}
}
}
int k;
int main(){
cin>>n>>m>>k;
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
l[u].push_back(mp(v,w));
l[v].push_back(mp(u,w));
for(int i=1;i<=k;i++){
l[u+n*i].push_back(mp(v+n*i,w));
l[v+n*i].push_back(mp(u+n*i,w));
l[u+n*(i-1)].push_back(mp(v+n*i,0));
l[v+n*(i-1)].push_back(mp(u+n*i,0));
}
}
for(int i=0;i<=k;i++)l[n*i].push_back(mp(n*(i+1),0));//大坑
dijkstra();
cout<<(dis[n*(k+1)]>1e9?-1:dis[n*(k+1)]);
}
```
by ReTF @ 2022-08-09 12:21:57