NC14700 追债之旅
题意：
有一个小偷，在n号点，他每天都会花费一定的钱，k天之后就会离开，你在1号点，存在m条边，每条边有一个花费，你每天只能走一条边，要求你在小偷离开之前抓到他，并且你自己行程所花的费用加上小偷的花费最少，求出满足上述题意的最少花费
做法：
分层图最短路，考虑将每一天的所有点看作一层图，所以对于你走一条边来说，实际上是从一层图走到了另一层图，并且在考虑花费的时候，需要考虑到当前是第几天，并把这一天的花费加在边权上面，最后找到在k天前到达n号点的最小花费即为答案，注意考虑不能到达的情况
代码：
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e4 + 5;
const ll mod = 20010905;
struct edge
{
int now;
ll w;
int nex;
}e[MAXN * 2];
int head[MAXN], tot;
ll dis[11][10005];
bool book[11][10005];
void init()
{
memset(head, -1, sizeof(head));
tot = 1;
}
void add(int a, int b, ll c)
{
e[tot] = edge{ b,c,head[a] };
head[a] = tot++;
}
ll cost[MAXN];
struct node
{
int now;
ll w;
int day;
};
auto cmp = [](node q, node w) {
return q.w > w.w;
};
void dij()
{
for (int i = 0; i < 11; i++)
for (int j = 2; j < 1005; j++)
dis[i][j] = 1e18;
priority_queue<node, vector<node>, decltype(cmp)>q(cmp);
q.push(node{ 1,0,0 });
while (!q.empty())
{
node u = q.top();
q.pop();
if (book[u.day][u.now])
continue;
book[u.day][u.now] = true;
for (int i = head[u.now]; i + 1; i = e[i].nex)
{
int v = e[i].now;
if (u.day + 1 > 10)
continue;
if (dis[u.day + 1][v] > dis[u.day][u.now] + cost[u.day + 1] + e[i].w)
{
dis[u.day + 1][v] = dis[u.day][u.now] + cost[u.day + 1] + e[i].w;
q.push(node{ v,dis[u.day + 1][v] ,u.day + 1 });
}
}
}
}
int main()
{
init();
int n, m, k;
sc("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i++)
{
int a, b; ll c;
sc("%d%d%lld", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
for (int i = 1; i <= k; i++)
{
sc("%lld", &cost[i]);
}
dij();
ll ans = 1e18;
for (int i = 0; i <= k; i++)
ans = min(ans, dis[i][n]);
if (ans == 1e18)
ans = -1;
pr("%lld\n", ans);
} 
CVTE公司福利 265人发布