Ruins He's house

直接构造优先队列，每次取出最小的两个数相加，直到队列中只有一个数为止，还是用 STL 过的题。

注意 priority_queue 的用法，原型：

1
2

priority_queue<Type> q;
priority_queue<Type, deque<Type>, Comp> q;

其中 Type 是类型，Comp 是比较结构体，比较函数是它的括号重载，比如对 int 型从小到大排序的 Comp 结构体如下：

1
2
3

struct Comp {
  bool operator()(const LL& a, const LL& b) const { return a > b; }
};

这题还要注意使用 long long，不然会越界导致 WA。

求逆序对的题目，可以用暴力、树状数组来实现。

这题用到了 STL 的强大功能，简单图论，但是需要进行 hash，我运用的是 map 来 hash。

首先是建图，将父子关系连有向边，从父亲到孩子，这样我们就可以通过 DFS 一遍找到全部的年龄。注意 map 的定义。最后用一个 rbt 来维护最后的解有序，当然，你也可以运用向量 vector 来维护，总的时间复杂度是 $O(nlgn)$ 的。

好吧，我承认这题很简单 (不会 STL 的孩子把这句话无视)，看错题目导致成功挂零。。。无语死了。。。

今天的 250 不是很难，要点有：

1. 对字符串的切割，手写切割函数比较保险，当然会用 STL 的字符串流的可以直接按照空格切割。
2. 查找关键字，嗯，这里有个好技巧，用红黑树 (set) 来维护全部的危险关键字即可。
3. 判断条件，只有当危险关键字超过定值的时候才是危险网站，否则不是。
4. 当一个网站是危险网站的时候，他的全部关键字都是危险的，这时候，我们要把全部的关键字加入红黑树中管理。
5. 由于 4 的原因，要扫描 $N$ 次 (类似贝尔曼福德算法)，加入的顺序就不是原来的顺序了，这里在最后对其 id 进行一次排序，可以用一个映射 map 来存储下标。

这题很囧的 7、8 次 WA 都贡献给了 I64d。。。好吧我承认这个 CF 很强大。。。

这题的思路如下：

首先用 Floyd 在 $O(n^3)$ 的时间复杂度内算出最短路总和 $ret$

更新的边 $(x, y)$ 长度是 $w$，那么如果 $w \geq dist[x][y]$ 就不做处理，输出这时的 $ret$

如果 $w<dist[x][y]$，那么枚举所有的结点，对结点 $j$ 和 $k$

$dist[j][k]$ 的值就是 $dist[j][k]$、$dist[j][x]+w+dist[y][k]$ 和 $dist[j][y]+w+dist[x][k]$ 中的最小值。

如果 $dist[j][k]$ 的新值比原来的小，那么就更新 $ret$ 的值。

为了优化时间，让 $j$ 大于 $i$，更新了 $dist[j][k]$ 后顺便把 $dist[k][j]$ 更新了

$$dist[k][j]=dist[j][k]$$