free
题意
给出一个带权联通无向图，你需要从s走到t，你可以选择k条变让他们的权值为0问从s到t的最小权值是多少？
分析
思考一下，如果不带k条白嫖这个条件，那么这就是一个简单的dji就搞定了，我们再来看k的范围1000 直接乘上dji的复杂度还能过，空间也开的下，所以直接一个二维dji就搞定了
#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
using namespace std;
#define pb push_back
#define F first
#define S second
#define mkp make_pair
const int maxn=1e3+5;
#define int ll
typedef long long ll;
const int inf=1e10;
int n,m,s,t,k,x,y,v;
int head[maxn],dist[maxn][maxn],vis[maxn][maxn];
struct ZZ{
int to,v,next;
}edge[maxn*4];
int cnt=0;
void add(int x,int y,int v){
edge[cnt].to=y;
edge[cnt].v=v;
edge[cnt].next=head[x];
head[x]=cnt++;
}
struct Node{
int v,id,cishu;
Node(int _v,int _id,int _cishu):v(_v),id(_id),cishu(_cishu){}
bool operator<(const Node&a)const {
return v>a.v;
}
};
priority_queue<Node>q;
void dij(){
for(int i=0;i<=n;i++){
for(int j=0;j<=k;j++){
vis[i][j]=0;
dist[i][j]=inf;
}
}
while(!q.empty())q.pop();
dist[s][k]=0;
q.push(Node(0,s,k));
while(!q.empty()){
auto tmp=q.top();
q.pop();
if(vis[tmp.id][tmp.cishu])continue;
vis[tmp.id][tmp.cishu]=1;
for(int i=head[tmp.id];i!=-1;i=edge[i].next){
int y=edge[i].to;
if(!vis[y][tmp.cishu]&&dist[y][tmp.cishu]>dist[tmp.id][tmp.cishu]+edge[i].v){
dist[y][tmp.cishu]=dist[tmp.id][tmp.cishu]+edge[i].v;
q.push(Node(dist[y][tmp.cishu],y,tmp.cishu));
}
if(tmp.cishu-1>=0&&!vis[y][tmp.cishu-1]&&dist[y][tmp.cishu-1]>dist[tmp.id][tmp.cishu]){
dist[y][tmp.cishu-1]=dist[tmp.id][tmp.cishu];
q.push(Node(dist[y][tmp.cishu-1],tmp.id,tmp.cishu-1));
}
}
}
ll ans=inf;
for(int i=0;i<=k;i++)ans=min(ans,dist[t][i]);
printf("%lld
",ans);
//cout<<dist[t][0]<<endl;
}
int32_t main(){
scanf("%lld%lld%lld%lld%lld",&n,&m,&s,&t,&k);
for(int i=0;i<=n;i++)head[i]=-1;
for(int i=0;i<m;i++){
scanf("%lld%lld%lld",&x,&y,&v);
add(x,y,v);
add(y,x,v);
// add(x,y,-1);
// add(y,x,-1);
}
dij();
return 0;
}