简答题 偏难
#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

5 5
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。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include &lt;cstdio&gt; #include &lt;algorithm&gt; #include &lt;vector&gt; #include &lt;queue&gt; using namespace std; const int N = 1e5 + 5; const long long oo = 1e18; int n, m; int a, b; int c[N]; vector&lt;pair&lt;int, int&gt;&gt; e[N]; long long dis[N]; priority_queue&lt;pair&lt;long long, int&gt;&gt; q; long long ans; int main() {     scanf("%d%d", &amp;n, &amp;m);     scanf("%d%d", &amp;a, &amp;b);     for (int i = 1; i &lt;= n; i++)         scanf("%d", &amp;c[i]);     for (int i = 1; i &lt;= m; i++) {         int u, v, w;         scanf("%d%d%d", &amp;u, &amp;v, &amp;w);         e[u].emplace_back(make_pair(v, w));         e[v].emplace_back(make_pair(u, w));     }     for (int i = 1; i &lt;= 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] &gt; dis[u] + w) {                 dis[v] = dis[u] + w;                 q.push(make_pair(-dis[v], v));             }         }     }     for (int i = 1; i &lt;= n; i++)         if (dis[i] &lt; dis[a])             ans += c[i];     printf("%lld\n", ans);     return 0; }</pre>
这道题暂未补解析。