Day 043 · 任务

题目

早做晚做都得做。

小J现在手上有 N 个任务还没有完成，任务之间都有一些关联，一共有 M 个关联。

每个任务根据难度不同都有一个难度值 a_i，由于任务之间的关联会导致任务复杂度上升，所以当我们完成第 i 个任务时，与其存在关联的未完成任务会为这个任务的完成带来额外代价，其具体值是这些存在关联的未完成任务的难度值之和。

现在小J想知道通过什么顺序来完成任务可以让额外代价最小。

小R表示它能够帮忙，但事实上他并不知道要怎么完成，现在希望你能够帮助他们求出最小的额外代价值。

输入：第一行两个数 N, M；第二行 N 个数，第 i 个数 a_i 表示 i 这个任务的难度；接下来 M 行，每行两个数 u, v，表示 u, v 两个任务存在关联。数据保证任意两个任务之间最多一条关联，并且不存在自环。
输出：你需要输出最小的额外代价是多少。

样例：

输入

4 3
40 20 30 10
1 4
2 4
2 3

输出

解释：一个合理的方法是先完成 1 号任务，此时有 10 点额外代价。接下来完成 3 号任务，获得 20 点额外代价，再完成 2 号任务，获得 10 点额外代价，最后完成 4 号任务，没有额外代价。总计 40 点额外代价。

提示：对于 30% 的数据，保证 1≤N≤10。对于 60% 的数据，保证 1≤N,M≤1000。对于 100% 的数据，保证 1≤N,M,a_i≤10⁵。

C++ · p69.cpp

今日感受