P4568 [JLOI2011] 飞行路线 题解

· · 题解

题意: 有 n 个点，由 m 条双向边连接。城市 a_i 与城市 b_i 之间有一条双向边，费用为 c 。共有 k 次免费机会。求最小费用
听起来就挺像DP
思路：由题面求最小可知，需要用到DP和最短路。鉴于还要搜索，加一个bfs。 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k,s,t,f[100001][21];
struct edge{
    ll nt,to,vl;
}p[1000001];
ll hd[1000001],nm;
void ad(ll x,ll y,ll z){
    p[++nm].nt=hd[x];
    p[nm].to=y;
    p[nm].vl=z;
    hd[x]=nm;
}
//建图ing
struct vs{
    ll x,vl;
    vs(ll a,ll b){
        x=a;
        vl=b;
    }
    bool operator <(const vs b) const{
        return vl>b.vl;
    }
};
//dfs ing
priority_queue<vs> q;
void djstl(){
    for(ll i=0;i<=k;i++)
        f[s][i]=0;
    for(ll i=0;i<=k;i++){
        q.push(vs(s,0));
        while(!q.empty()){
            vs u=q.top();
            q.pop();
            if(u.vl>f[u.x][i]) continue;
            for(ll j=hd[u.x];j;j=p[j].nt){
                ll v=p[j].to;
                bool bl=0;
                if(i)
                    if(f[v][i]>f[u.x][i-1]){
                        f[v][i]=f[u.x][i-1];
                        bl=1;
                    }
                if(f[v][i]>f[u.x][i]+p[j].vl){
                    f[v][i]=f[u.x][i]+p[j].vl;
                    bl=1;
                }
                if(bl) q.push(vs(v,f[v][i]));
            }
        }
    }
}
//DPing
int main(){
    cin>>n>>m>>k>>s>>t;
    for(ll i=1;i<=m;i++){
        ll x,y,z;
        cin>>x>>y>>z;
        ad(x,y,z);
        ad(y,x,z);
    }
    for(ll i=0;i<n;i++)
        for(ll j=0;j<=k;j++)
            f[i][j]=1e9;
    djstl();
    cout<<f[t][k];
    return 0;
}
//没了

此代码成分复杂，没有危险，可放心使用。