<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
1128.信使
战争时期,前线有 $n$ 个哨所,每个哨所可能会与其他若干个哨所之间有通信联系。
信使负责在哨所之间传递信息,当然,这是要花费一定时间的(以天为单位)。
指挥部设在第一个哨所。
当指挥部下达一个命令后,指挥部就派出若干个信使向与指挥部相连的哨所送信。
当一个哨所接到信后,这个哨所内的信使们也以同样的方式向其他哨所送信。信在一个哨所内停留的时间可以忽略不计。
直至所有 $n$ 个哨所全部接到命令后,送信才算成功。
因为准备充足,每个哨所内都安排了足够的信使(如果一个哨所与其他 $k$ 个哨所有通信联系的话,这个哨所内至少会配备 $k$ 个信使)。
现在总指挥请你编一个程序,计算出完成整个送信过程最短需要多少时间。
输入格式
第 $1$ 行有两个整数 $n$ 和 $m$,中间用 $1$ 个空格隔开,分别表示有 $n$ 个哨所和 $m$ 条通信线路。
第 $2$ 至 $m+1$ 行:每行三个整数 $i、j、k$,中间用 $1$ 个空格隔开,表示第 $i$ 个和第 $j$ 个哨所之间存在 双向 通信线路,且这条线路要花费 $k$ 天。
输出格式
一个整数,表示完成整个送信过程的最短时间。
如果不是所有的哨所都能收到信,就输出-1。
数据范围
$1 \le n \le 100$,
$1 \le m \le 200$,
$1 \le k \le 1000$
输入样例:
4 4
1 2 4
2 3 7
2 4 1
3 4 6
输出样例:
11
算法:$dijkstra$ 堆优化
和 1129
题十分相似,为了水长度再放一遍变量解释:
$n$:节点个数 $m$:边的个数 $s$:起点编号 $e$:中点编号
$d[i]$:$distance$ 间距,表示当前从起点到点 $i$ 的最短路径的最小值
$v[i]$:$visit$ 访问,表示当前有没有访问(更新)节点 $i$
$struct$ $node$ { $int$ $to,$ $w$ }:$edge$ 边, $to$ 表示边的终点,$w$ 表示边的权值
$vector$ <$node$> $vec[i][j]$:$edge$ 存边(仅仅是作者习惯,向量命名为 $vec$ ),表示起点为 $i$ 的第 $j$ 条边 (终点为 $vec[i][j].to$,权值为 $vec[i][j].w$ )
注意,这题的目标是求 $d$ 数组中的最大值,注意判断无解的情况
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 2000009, INF = 1e9;
struct node
{//node存放边
int to, w;
//to表示路径终点,w表示路径权值
bool operator <(const node &x) const
{
if(w == x.w) return to > x.to;
else return w > x.w;
}
};
bool v[N];//记录节点有没有被访问
int d[N];//记录每一个节点到起点最短路
int n;//节点个数
int m;//边的个数
int s, e;//起点与终点
int ans = 0;//答案,计数可得
vector <node> vec[N];
priority_queue <node> q;//优先队列
bool dijkstra(int x)
{
for(int i = 1;i <= n;++ i) d[i] = INF, v[i] = false;
//一开始,所有边都不与起点连通
d[x] = 0;//起点到自己的距离为0
q.push((node){x, 0});//起点入队
while(!q.empty())
{
node e = q.top(), tmp; q.pop();
v[e.to] = true;
for(int i = 0;i < vec[e.to].size();++ i)
{
tmp = vec[e.to][i];
if(v[tmp.to]) continue;
if(d[tmp.to] > d[e.to] + tmp.w)
{
d[tmp.to] = d[e.to] + tmp.w;
// cout << e.to << " " << tmp.to << " " << d[tmp.to] << endl;
q.push((node) {tmp.to, d[tmp.to]});
}
}
}
for(int i = 1;i <= n;++ i)
if(d[i] == INF) return false;
else ans = max(ans, d[i]);
return true;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1, u, v, w;i <= m;++ i)
{//u代表路径起点,v代表路径终点,w代表路径长度
cin >> u >> v >> w;
vec[u].push_back((node) {v, w});//建边
vec[v].push_back((node) {u, w});//建反边
//因为是无向图,建两条边
}
if(dijkstra(1)) cout << ans << endl;//从起点开始
else cout << -1 << endl;//无解
return 0;
}