追债之旅

题目地址：

https://ac.nowcoder.com/acm/problem/14700

基本思路：

比较容易看出是一个最短路,我们把每个点,根据个到达时间拆成个点,
然后我们一样跑,只是在的过程中多记录一下耗时就行了。
最后我们在里取最小值就是答案了,如果都不能到达那就输出-1。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}


const int maxn = 1010;
struct Node {
    int w, d, u;
    bool operator<(const Node &no) const {
      return w > no.w;
    }
};
int n,m,k,a[maxn];
int cnt = 0, head[maxn];
struct Edge {
    int next, to, w;
} edge[20010];
void init() {
  cnt = 0;
  memset(head, -1, sizeof(head));
}
void add_edge(int u, int v, int w) {
  edge[++cnt] = {head[u], v, w};
  head[u] = cnt;
}
bool vis[20][maxn];
int dis[20][maxn];
void dijkstra() {
  mset(dis, INF);
  mset(vis,false);
  priority_queue<Node> que;
  dis[0][1] = 0;
  que.push({0, 0, 1});
  while (!que.empty()) {
    int u = que.top().u, d = que.top().d;
    que.pop();
    if (vis[d][u]) continue;
    vis[d][u] = true;
    for (int i = head[u]; i != -1; i = edge[i].next) {
      int to = edge[i].to;
      if (d + 1 <= k && dis[d + 1][to] > dis[d][u] + edge[i].w + a[d + 1]) {
        dis[d + 1][to] = dis[d][u] + edge[i].w + a[d + 1];
        que.push({dis[d + 1][to], d + 1, to});
      }
    }
  }
}
signed main() {
  IO;
  cin >> n >> m >> k;
  init();
  rep(i,1,m){
    int u,v,w;
    cin >> u >> v >> w;
    add_edge(u,v,w);
    add_edge(v,u,w);
  }
  for(int i = 1 ; i <= k ; i++) cin >> a[i];
  dijkstra();
  int ans = INF;
  for(int i = 0 ; i <= k ; i++) ans = min(ans,dis[i][n]);
  if(ans == INF) cout << -1 << '\n';
  else cout << ans << '\n';
  return 0;
}