NC14700（追债之旅 ）

感受

思路

AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const ll inf = 1e18;
struct edge{
    ll w;
    int to;
};
struct P{
    ll dis;
    int to;
    bool operator < (const P& b)const{
        return dis > b.dis;
    }
};
ll d[maxn];
int n, m, s, t, k;
vector<edge> G[maxn];
void add_edge(int u, int v, ll w){
    G[u].push_back({w, v});
}
void dij(int s, int n){
    for(int i = 1; i <= n; i++) d[i] = inf;///首先初始化
    priority_queue<P>que;
    que.push({0, s});
    d[s] = 0;
    while(!que.empty()){
        P tmp = que.top(); que.pop();
        int u = tmp.to; ll dis = tmp.dis;
        if(d[u] < dis) continue;///如果当前点u已经达到最优解，就不需要用这个不优的解去更新它的邻边
        for(int i = 0; i < G[u].size(); i++){
            edge e = G[u][i];
            int v = e.to; ll w = e.w;
            if(d[v] > d[u] + w){
                d[v] = d[u] + w;
                que.push({d[v], v});
            }
        }
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    int u, v; ll w;
    for(int i = 1; i <= m; i++){
        scanf("%d%d%lld", &u, &v, &w);
        for(int j = 0; j < k; j++){
            add_edge(u + j * n, v + (j + 1) * n, w);
            add_edge(v + j * n, u + (j + 1) * n, w);
        }
    }
    s = 1; t = (k + 1) * n + 1;
    ll sum = 0, val; add_edge(n, t, 0);
    for(int i = 1; i <= k; i++){
        scanf("%lld", &val);
        sum += val;
        add_edge(n + i * n, t, sum);
    }
    dij(s, t);
    if(d[t] == inf){
        puts("-1");
    }
    else{
        printf("%lld\n", d[t]);
    }
    return 0;
}