每日一题 追债之旅 (bfs)

一.题意

n 个城市，m 条路
小明在 1 城，欠债人在 n 城
小明经过一条路需要一定花费，欠债人第 i 天会挥霍 的钱
求小明花费的最小值最小值

二.题解

when

三.代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define eps 1e-10
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
inline ll read(){
   ll s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

const int manx=1e3+5;
const int N=5e2+5;
const int mod=1e9+7;

ll n,m,k,ans=inf;
struct node{
    ll u,w,d;
    bool operator< (const node &x)const{
        return w>x.w;
    }
};
vector<pair<ll,ll> >g[manx];
ll dp[manx][11],a[15];
priority_queue<node>q;

void bfs(){
    memset(dp,inf,sizeof(dp));
    dp[1][0]=0;
    q.push((node){1,0,0});
    while(q.size()){
        node x=q.top(); q.pop();
        ll u=x.u,w=x.w,d=x.d;
        for(auto pi: g[u]){
            ll v=pi.fi,cost=pi.se;
            if(d+1<=k&&dp[u][d]+cost+a[d+1]<dp[v][d+1]){
                dp[v][d+1]=dp[u][d]+cost+a[d+1];
                q.push((node){v,dp[v][d+1],d+1});
            }
        }
    }
}

int main(){
    io; cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        ll u,v,w; cin>>u>>v>>w;
        g[u].pb({v,w});  g[v].pb({u,w});
    }
    for(int i=1;i<=k;i++) cin>>a[i];
    bfs();
    for(int i=1;i<=k;i++) ans=min(ans,dp[n][i]);
    if(ans!=inf) cout<<ans<<endl;
    else cout<<-1<<endl;
}