A22072. 猫和⽼⿏
填空题
困难
知识点
题目描述
猫和⽼⿏
题目描述
猫和老鼠所在的庄园可以视为一张由 n 个点和 m 条带权无向边构成的连通图。结点依次以 1,2,…,n 编号，结点 i（1 ≤ i ≤ n）有价值为 ci 的奶酪。在 m 条带权无向边中，第 i（1 ≤ i ≤ m）条无向边连接结点 ui 与 vi，边权 wi 表示猫和老鼠通过这条边所需的时间。
猫窝位于结点 a，老鼠洞位于结点 b。对于老鼠而言，结点 u 是安全的当且仅当：
- 老鼠能规划一条从结点 u 出发逃往老鼠洞的路径，使得对于路径上任意结点 x（包括结点 u 与老鼠洞）都有：猫从猫窝出发到结点 x 的最短时间严格大于老鼠从结点 u 沿这条路径前往结点 x 所需的时间。
老鼠在拿取安全结点的奶酪时不存在被猫抓住的可能，但在拿取不是安全结点的奶酪时则不一定。为了确保万无一失，老鼠决定只拿取安全结点放置的奶酪。请你计算老鼠所能拿到的奶酪价值之和。
输入格式
第一行，两个正整数 n,m，分别表示图的结点数与边数。
第二行，两个正整数 a,b，分别表示猫窝的结点编号，以及老鼠洞的结点编号。
第三行，n 个正整数 c1,c2,…,cn，表示各个结点的奶酪价值。
接下来 m 行中的第 i 行（1 ≤ i ≤ m）包含三个正整数 ui ,vi,wi ，表示图中连接结点 ui 与结点 vi 的边，边权为 wi。
输出格式
输出一行，一个整数，表示老鼠所能拿到的奶酪价值之和。
样例
输入样例 1
55
1 2
1 2 4 8 16
1 2 4
2 3 3
3 4 1
2 5 2
3 1 8输出样例 1
22输入样例 2
6 10
3 4
1 1 1 1 1 1
1 2 6
2 3 3
3 1 4
3 4 5
4 5 8
5 6 2
6 4 1
3 2 4
5 4 4
3 3 6输出样例 2
3数据范围
对于 40 的测试点，保证 1 ≤ n ≤ 500，1 ≤ m ≤ 500。
对于所有测试点，保证 1 ≤ n ≤ 105，1 ≤ m ≤ 105，1 ≤ a,b ≤ n 且 a ≠ b，1 ≤ ui ,vi≤ n，1 ≤ wi ≤ 109。
参考答案
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N = 1e5 + 5;
const long long oo = 1e18;
int n, m;
int a, b;
int c[N];
vector<pair<int, int>> e[N];
long long dis[N];
priority_queue<pair<long long, int>> q;
long long ans;
int main() {
scanf("%d%d", &n, &m);
scanf("%d%d", &a, &b);
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[u].emplace_back(make_pair(v, w));
e[v].emplace_back(make_pair(u, w));
}
for (int i = 1; i <= n; i++)
dis[i] = oo;
dis[b] = 0;
q.push(make_pair(-dis[b], b));
while (!q.empty()) {
auto p = q.top();
q.pop();
if (dis[p.second] != -p.first)
continue;
int u = p.second;
for (auto r : e[u]) {
int v = r.first, w = r.second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push(make_pair(-dis[v], v));
}
}
}
for (int i = 1; i <= n; i++)
if (dis[i] < dis[a])
ans += c[i];
printf("%lld\n", ans);
return 0;
}
上一题
下一题