AI题库 · GESP-C++八级题库
题目分享 #19754
猫和老鼠
时间限制: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。
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。