340. 通信线路（spfa）

asd1926 · 2021-07-22 20:23:38 · 个人记录

//f[i][j]：在一条路中前i条电缆中，选择j个免费的最小花费
//f[i][j] = f[x][j] + g[x][i];不选第i条电缆
//f[i][j] = min (f[i][j], f[i - 1][j - 1]);

#include <iostream>
#include <queue>
#include <deque>
#include <cstring>
using namespace std;

const int N = 2e4 + 10;

int n, p, k;
bool st[N][N];
int dist[10100][1010];
int h[N], e[N], ne[N], w[N], idx;

void add (int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
void bfs () {
    memset (dist, 0x3f, sizeof dist);
    dist[1][0]= 0;
    queue<pair<int, int>> q;
    q.push({1, 0});
    while(q.size()) {
        auto t = q.front();q.pop();
        int x = t.first, m = t.second;
        st[x][m] = 0;

        for (int i = h[x]; i != -1; i =ne[i]) {
            int y = e[i];
            if (max(dist[x][m], w[i]) < dist[y][m]) {
                dist[y][m] = max (dist[x][m], w[i]);
                if (!st[y][m]) {
                    q.push({y, m});
                    st[y][m] = true;
                }

            }
            if (m + 1 <= k && dist[x][m] < dist[y][m + 1]) {
                dist[y][m + 1] = dist[x][m];
                q.push({y, m + 1});
                if (!st[y][m]) {
                    q.push({y, m + 1});
                    st[y][m] = true;
                }
            }
        }
    }

}
int main () {
    memset (h, -1, sizeof h);
    cin >> n >>p >>k;
    for (int i = 0; i < p; i ++) {
        int a, b, w;
        cin >> a >> b >>w;
      add (a, b, w); add (b, a, w);
    }

   bfs ();
    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= k; i ++) ans = min (ans, dist[n][i]);
    if (ans == 0x3f3f3f3f) puts ("-1");
    else {
        cout << ans << endl;
    }
    return 0;
}
方法:松弛操作
f[i][j]表示前i个点已经选择不超过j个的最小值