Telephone Lines

Telephone Lines

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=1010;
struct edge{
    int v,next,w;
}e[maxn*10];

int t,head[maxn],n,m,k,vis[maxn],f[maxn][maxn];

void add(int u,int v,int w){
    t++;
    e[t].v=v;
    e[t].w=w;
    e[t].next=head[u];
    head[u]=t;
}

int spfa_dp() {
    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;
    vis[1] = 1;
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            for (int j = 0; j <= k; j++) {
                int tt = f[v][j];
                if (j) f[v][j] = min(f[v][j], f[u][j - 1]);
                f[v][j] = min(f[v][j], max(f[u][j], e[i].w));
                if (tt != f[v][j] && vis[v] == 0) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
        vis[u] = 0;
    }
    if (f[n][k] == 0x3f3f3f3f) return -1; else return f[n][k];
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, u, v, w; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }
    printf("%d\n", spfa_dp());
    return 0;
}

Telephone Lines

原文：https://www.cnblogs.com/Accpted/p/11388960.html