在战争时期,有 n 个哨所,它们之间通过 m 条通信线路相连。每个哨所可以通过这些通信线路传递信息,但传递信息需要花费不同的时间。

指挥部位于第一个哨所,当指挥部下达命令时,若干信使将被派遣到与指挥部相连的哨所传递信息。然后,这些哨所的信使会继续将信息传递给其他哨所,直到所有 n 个哨所都接收到命令为止。

每个哨所都有足够的信使,且每个哨所最多与其他 k 个哨所有通信线路。

编写一个程序来计算完成整个送信过程的最短时间,如果无法让所有哨所都接收到信,输出-1。

输入格式:

  • 第一行包含两个整数 n 和 m,表示哨所的数量和通信线路的数量。
  • 接下来的 m 行每行包含三个整数 i、j、k,表示哨所 i 和哨所 j 之间的通信线路需要花费 k 天。

输出格式:

  • 一个整数,表示完成整个送信过程的最短时间,或者输出-1。

数据范围:

  • 1 ≤ n ≤ 100
  • 1 ≤ m ≤ 200
  • 1 ≤ k ≤ 1000

示例输入:

4 4
1 2 4
2 3 7
2 4 1
3 4 6

示例输出:

11

思路

堆优化 Dijikstra

代码实现

#include <iostream>
#include <queue>
#include <bitset>
#include <cstring>
#define x first
#define y second
using namespace std;
using PII = pair <int,int>;
const int N = 1e3;

priority_queue <PII, vector <PII>, greater <PII>> heap;
int n, m, idx, h[N], ne[N], w[N], e[N], dist[N];
bitset <N> st;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dijikstra() {
    int ans = 0;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    heap.push({0,1});
    while(heap.size()) {
        auto t = heap.top(); heap.pop();
        if (st[t.y]) continue;
        st[t.y] = 1;
        ans = t.x;
        for (int i = h[t.y]; ~i; i = ne[i]) {
            auto& j = e[i];
            if (dist[j] > dist[t.y] + w[i]) {
                dist[j] = dist[t.y] + w[i];
                heap.push({dist[j],j});
            }
        }
    }
    if (st.count() != n) return -1;
    return ans;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a,b,c), add(b,a,c);
    }
    cout << dijikstra();
    return 0;
}
分类: Dijkstra

0 条评论

发表回复

Avatar placeholder

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

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

站点状态:Status