题解 | #追债之旅#

有边数限制的最短路 —— bellman_ford 模板题

时间复杂度 O（nm）

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 20010;

struct node{
    int a,b,w;
}p[M];
int a[N];
int sum[N];
int dist[N];
int backup[N];
int n,m,k;
int t;

int bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    int ans=1e9;
    for(int i=1;i<=k;i++){
        memcpy(backup,dist,sizeof dist);
        for(int j=0;j<t;j++) {
            int a=p[j].a,b=p[j].b,w=p[j].w;
            if(dist[b]>backup[a]+w){
                dist[b]=backup[a]+w;
                if(b==n) ans=min(ans,dist[n]+sum[i]);    //更新总花费
            }
        }
    }

    if(dist[n]==0x3f3f3f3f) return -1;   //无法到达n点
    return ans;
}

int main(){
    cin>>n>>m>>k;

    while(m--) {
        int a,b,w;
        cin>>a>>b>>w;
        p[t++]={a,b,w};
        p[t++]={b,a,w};
    }
    for(int i=1;i<=k;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];

    int x=bellman_ford();
    cout<<x<<endl;

    return 0;
}