指名专题

愚者指名自己的辩护人_纪中2046_最短路_维包一生推,gosick大法好!

输入 第一行两个整数 N,M,表示点数和边数。 接下来一行 N 个整数,第 i 个正整数表示 Pi。 接下来 M 行,每行两个整数 u,v,表示有一条无向边连接了 u 和 v。 输出 输出 N 行,每行为一个 0 或 1,意义如题目描述所示。 题解 枚举去掉哪些点会对结果产生影响,就是必定经过的点 精度是个问题需要注意 spfa是最快的,复杂度 O(nmk)

2046. 愚者指名自己的辩护人

2046. 愚者指名自己的辩护人  输入 第一行两个整数 N,M,表示点数和边数。 接下来一行 N 个整数,第 i 个正整数表示 Pi。 接下来 M 行,每行两个整数 u,v,表示有一条无向边连接了 u 和 v。 输出 输出 N 行,每行为一个 0 或 1,意义如题目描述所示。 样例输入 7 8 1 50 49 10 90 90 1 1 2 1 3 2 4 3 4 4 5