追债之旅 | 最短路变式

n<=1000

其实n<=10000应该也可以做

考虑dis[i][k]代表从1出发到达i点经历了k条边的最小花费

所以更新的话，也就像最短路那么去更新了

 if dis[e][k+1] > dis[i][k] + w :
        dis[e][k+1] = dis[i][k] + w;

Code:

代码任何不懂的地方都可以直接在评论区指出！有问必回！

/*** keep hungry and calm CoolGuang!***/
ll n,m,p;
struct node{
    int id,t,c;
};
vector<pair<int,int>>v[maxn];
ll dis[1500][150];
void bfs(){

    queue<node>q;
    q.push(node{1,0,0});
    for(int i=1;i<=n;i++){
        for(int k=0;k<=m;k++){
            dis[i][k] = INF;
        }
    }
    dis[1][0] = 0;
    while(!q.empty()){
        node u = q.front();q.pop();
       /// if(dis[u.id][u.t]<u.c) continue;
        if(u.t >= p) continue;
      //  debug(1);
        for(auto x:v[u.id]){
            int d = u.t+1;
            int e = x.first;
            if(dis[e][d]>u.c+x.second){
                dis[e][d] = u.c+x.second;
                q.push(node{e,d,dis[e][d]});
            }
        }
    }
}
int main(){
    read(n);read(m);read(p);
    for(int i=1;i<=m;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        v[x].push_back({y,w});
        v[y].push_back({x,w});
    }
    bfs();
    ll ans = INF,tmp = 0;
    for(int i=1;i<=p;i++){
        ll x;read(x);
        tmp += x;
        if(dis[n][i]!=INF) ans = min(ans,dis[n][i]+tmp);
    }
    printf("%lld\n",ans==INF?-1*1ll:ans);
    return 0;
}
/***
3
3 20
2 1 8
3 1 7
6 1
1 2 1
2 3 1
2 6 1
3 4 1
3 5 1
***/