2019牛客多校第四场J free 最短路

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\n",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;

}