做网站服务器怎么用,温州网站设计制作,wordpress网站重新安装插件,望野赏析[蓝桥杯 2022 国 B] 出差
题目描述 A \mathrm{A} A 国有 N N N 个城市#xff0c;编号为 1 … N 1 \ldots N 1…N 小明是编号为 1 1 1 的城市中一家公司的员工#xff0c;今天突然接到了上级通知需要去编号为 N N N 的城市出差。
由于疫情原因#xff0c;很多直达的交…[蓝桥杯 2022 国 B] 出差
题目描述 A \mathrm{A} A 国有 N N N 个城市编号为 1 … N 1 \ldots N 1…N 小明是编号为 1 1 1 的城市中一家公司的员工今天突然接到了上级通知需要去编号为 N N N 的城市出差。
由于疫情原因很多直达的交通方式暂时关闭小明无法乘坐飞机直接从城市 1 1 1 到达城市 N N N需要通过其他城市进行陆路交通中转。小明通过交通信息网查询到了 M M M 条城市之间仍然还开通的路线信息以及每一条路线需要花费的时间。
同样由于疫情原因小明到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市。通过网络小明也查询到了各个城市的隔离信息。由于小明之前在城市 1 1 1因此可以直接离开城市 1 1 1不需要隔离
由于上级要求小明希望能够尽快赶到城市 N \mathrm{N} N, 因此他求助于你希望你能帮他规划一条路线能够在最短时间内到达城市 N N N 。
输入格式
第 1 1 1 行两个正整数 N , M N, M N,M 表示 A 国的城市数量, M M M 表示末关闭的路线数量。
第 2 2 2 行: N N N 个正整数第 i i i 个整数 C i C_{i} Ci 表示到达编号为 i \mathrm{i} i 的城市后需要隔离的时间。
第 3 … M 2 3 \ldots M2 3…M2 行: 每行 3 3 3 个正整数, u , v , c u, v, c u,v,c, 表示有一条城市 u u u 到城市 v v v 的双向路线仍然开通着通过该路线的时间为 c c c。
输出格式
第 1 1 1 行 1 1 1 个正整数表示小明从城市 1 1 1 出发到达城市 N N N 的最短时间。到达城市 N N N不需要计算城市 N N N 的隔离时间
样例 #1
样例输入 #1
4 4
5 7 3 4
1 2 4
1 3 5
2 4 3
3 4 5样例输出 #1
13提示
【样例说明】 【评测用例规模与约定】
对于 100 % 100 \% 100% 的数据, 1 ≤ N ≤ 1000 , 1 ≤ M ≤ 10000 , 1 ≤ C i ≤ 200 , 1 ≤ u , v ≤ 1 \leq N \leq 1000,1 \leq M \leq 10000,1 \leq C_{i} \leq 200,1 \leq u, v \leq 1≤N≤1000,1≤M≤10000,1≤Ci≤200,1≤u,v≤ N , 1 ≤ c ≤ 1000 N, 1 \leq c \leq 1000 N,1≤c≤1000
蓝桥杯 2022 国赛 B 组 E 题。 思路
首先从输入中读取城市数量 n 和开放的路线数量 m。然后读取每个城市的隔离时间存储在数组 c 中。接着读取 m 条边的信息每条边包含起始城市 u目标城市 v以及通过该路线需要的时间 w。对于每条边都将其添加到链式前向星中同时将该城市的隔离时间加到边的权重上。这样做的目的是在计算从城市 u 到城市 v 的时间时同时考虑了在城市 v 的隔离时间。
通过 Dijkstra 算法来找到从城市 1 到城市 n 的最短路径。使用 vis.reset() 初始化所有节点为未访问状态。然后对于每个节点如果节点是源点城市 1则其到自己的最短距离 dist[i] 为 0并将其加入优先队列 hmin 中。否则将其最短距离设置为无穷大并将其前驱节点 prior[i] 设置为 -1表示还没有找到到达它的最短路径。
然后进入主循环当优先队列不为空时取出队列顶部的节点 t其中 t.v 是节点编号t.d 是从源点到该节点的当前最短距离。如果该节点已经被访问过则跳过。否则将其标记为已访问。然后遍历从节点 u 出发的所有边如果通过当前边到达节点 v 的距离 du edge[i].w 小于 v 的当前最短距离 dist[v]则更新 dist[v]并将 v 加入优先队列。
这个过程会持续直到优先队列为空或者找到目标节点 n。注意dist[v] 中的值是从源点到达 v 并在 v 进行隔离的总时间所以在最后的结果中需要减去城市 n 的隔离时间。
注意
到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市将终点城市的隔离时间加到边的权重上即可。到达城市 n 后不需要隔离所以在最后的结果中需要减去城市 n 的隔离时间。 AC代码
#include algorithm
#include bitset
#include cmath
#include cstring
#include iostream
#include queue
#define AUTHOR HEX9CF
using namespace std;
using ll long long;const int N 1e6 7;
const int INF 0x3f3f3f3f;
const ll MOD 1e9 7;struct Edge {int w, to, next;
} edge[N];
int head[N];
int cnt 0;struct Node {int v, d;bool operator(const Node b) const { return d b.d; }
};int n, m;
int c[N];// 最短路径长度
int dist[N];
// 前驱节点
int prior[N];
bitsetN vis;
priority_queueNode hmin;void add(int u, int v, int w) {edge[cnt] {w, v, head[u]};head[u] cnt;
}void dijkstra() {vis.reset();for (int i 1; i n; i) {if (i 1) {dist[i] 0;hmin.push({i, 0});} else {dist[i] INF;prior[i] -1;}}while (hmin.size()) {auto t hmin.top();hmin.pop();int u t.v;int du t.d;if (vis[u]) {continue;}vis[u] 1;for (int i head[u]; ~i; i edge[i].next) {int v edge[i].to;if (dist[v] (du edge[i].w)) {dist[v] du edge[i].w;prior[v] u;hmin.push({v, dist[v]});}}}
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(head, -1, sizeof(head));cin n m;for (int i 1; i n; i) {cin c[i];}for (int i 1; i m; i) {int u, v, w;cin u v w;// 到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市add(u, v, w c[v]);add(v, u, w c[u]);}dijkstra();// 到达n城后不需要隔离cout dist[n] - c[n] \n;return 0;
}
