7.1 追债之旅

题目链接

追债之旅

题目思路

用 dist[N][K] 来记录第几天到达第几个点, 用dijkstra算法来求值
最后遍历 dist[n][i] 求最小值

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, pair<int, int> > PII;

const int N = 1010, M = 20010;

int e[M], ne[M], w[M], h[N], idx, dist[N][20];
int n, m, k, a[N], s[N], res;
bool st[N][20];

void add(int u, int v, int x)
{
    e[idx] = v, w[idx] = x, ne[idx] = h[u], h[u] = idx ++ ;
}

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);

    priority_queue<PII, vector<PII>, greater<PII> > heap;

    heap.push({0, {1, 0}});

    dist[1][0] = 0;

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int d = t.first, ver = t.second.first, day = t.second.second;

        if (st[ver][day]) continue;
        st[ver][day] = true;

        if (day + 1 > k) continue;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];

            if (dist[j][day + 1] > d + w[i])
            {
                dist[j][day + 1] = d + w[i];
                heap.push({dist[j][day + 1], {j, day + 1}});
            }
        }
    }
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);

    memset(h, -1, sizeof h);

    cin >> n >> m >> k;

    while (m -- )
    {
        int u, v, x;
        cin >> u >> v >> x;
        add(u, v, x), add(v, u, x);
    }

    for (int i = 1; i <= k; i ++ ) 
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }

    dijkstra();

    res = 0x3f3f3f3f;

    for (int i = 1; i <= k; i ++ )
    {
        res = min(res, dist[n][i] + s[i]);
    }

    if (res == 0x3f3f3f3f) cout << -1 << endl;
    else cout << res << endl;

    return 0;
}