简答题
偏难
#19754
猫和老鼠 时间限制:1.0 s 内存限制:512.0 MB 题目描述 猫和老鼠所在的庄园可以视为一张由n个点和m条带权无向边构成的连通图。结点依次以1,2,..…
猫和老鼠
时间限制:1.0 s
内存限制:512.0 MB
题目描述
猫和老鼠所在的庄园可以视为一张由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,表示各个结点的奶酪价值。
接下来 行中的第i行(1≤x≤m)包含三个正整数ui,vi,wi,表示图中连接结点ui与结点vi的边,边权为wi。
输出格式
输出一行,一个整数,表示老鼠所能拿到的奶酪价值之和。
输入样例 1
输出样例 1
输入样例 2
输出样例 2
数据范围
对于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。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#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;
}</pre>
这道题暂未补解析。