在郊区有 N 座通信基站,P 条双向电缆,第 i 条电缆连接基站 AiBi

特别地,1 号基站是通信公司的总站,N 号基站位于一座农场中。

现在,农场主希望对通信线路进行升级,其中升级第 i 条电缆需要花费 Li

电话公司正在举行优惠活动。

农产主可以指定一条从 1 号基站到 N 号基站的路径,并指定路径上不超过 K 条电缆,由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中,升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

输入格式

第 1 行:三个整数 N, P, K

接下来的 P 行:每行包含三个整数 Ai, Bi, Li,表示电缆连接的两个基站编号和升级花费。

输出格式

包含一个整数,表示最少花费。

1 号基站与 N 号基站之间不存在路径,则输出 -1

数据范围

  • 0 ≤ K < N ≤ 1000
  • 1 ≤ P ≤ 10000
  • 1 ≤ Li ≤ 1000000

输入样例

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

输出样例

4

代码实现

#include <iostream>
#include <queue>
#include <bitset>
#include <cstring>
using namespace std;
const int N = 1e3 + 10;

int g[N][N], n, m, k;
int check(int mid) {
    int dist[N];
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    bitset <N> st;
    st[1] = 1;
    queue <int> que;
    que.push(1);
    while(que.size()) {
        auto t = que.front(); que.pop();
        st[t] = 0;
        for (int i = 1; i <= n; ++i) {
            if (g[t][i] != 0x3f3f3f3f) {
                if(dist[i] > dist[t] + (g[t][i] > mid)) {
                    dist[i] = dist[t] + (g[t][i] > mid);
                    if (!st[i]) {
                        st[i] = 1;
                        que.push(i);
                    }
                }
            }
        }
    }
    return dist[n];
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(g, 0x3f, sizeof g);
    cin >> n >> m >> k;
    for (int i = 0; i <= n; ++i) g[i][i] = 0;
    int l = 0, r = 0;
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        r = max(r,c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    while(l <= r) {
        int mid = ((r - l) >> 1) + l, t = check(mid);
        if (t == 0x3f3f3f3f) {
            cout << -1;
            return 0;
        }
        if (t > k) l = mid + 1;
        else r = mid - 1;
    }
    cout << l;
    return 0;
} 
分类: Binary-SearchSPFA

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status