#836x8r. 联合权值（link）

时间限制：200 ms       空间限制：128 MiB       标签： 图论 三元环计数 

算法难度等级：4       思维难度等级：5       实现难度等级：4

题目描述

无向连通图 $G$ 有 $n$ 个点， $m$ 条边。点从 $1$ 到 $n$ 编号，编号为 $i$ 的点权值为 $W_i$ 。每条边长度都为 $1$ 。对于图 $G$ 上的三元组 $(u,v,w)$ ，如果 $u-w-v$ 是 $(u,v)$ 之间的一条最短路（这里 $w$ 指和 $u,v$ 之间均有直接连边），则它将产生 $W_u \times W_v$ 的联合权值。换句话说，就是产生权值当且仅当 $(u,\ w)$ 之间有边，$(w,\ v)$ 之间有边，且 $(u,\ v)$ 之间没边。

请问图 $G$ 上所有可产生联合权值的三元组中，联合权值最大的是多少？所有联合权值之和是多少？

输入格式

输入文件的第一行为三个整数 $n,m,t$ 。其中 $t$ 是数据类型。

接下来 $m$ 行，每行两个正整数 $u,v$ ，表示图中的一条边。数据保证不存在重边或自环的情况。

输入数据的最后一行是 $n$ 个正整数，表示 $W_1,W_2,...,W_n$ 。

输出格式

输出文件共包含两行两个整数。第一行，若 $t\neq 2$ ，则你需要输出最大的联合权值（无则输出 $-1$ ），否则输出 $0$ ；第二行，若 $t\neq 1$ ，则你需要输出联合权值的总和，否则输出 $0$ 。

换句话说，就是 $t=1$ 时只需要求最大值，$t=2$ 时只需要求和，$t=3$ 时两个都要求。

4 4 3
1 2
1 3
2 3
2 4
100 1 100 1

100
400

样例 3

见附件 link2.in 和 link2.ans。

数据范围

对于 $20\%$ 的数据，满足 $n\leq 100$。

对于 $40\%$ 的数据，满足 $n\leq 1000$。

对于另 $20\%$ 的数据，满足 $t=1$。

对于另 $20\%$ 的数据，满足 $t=2$。

对于 $100\%$ 的数据，满足 $1\leq n,\ m\leq 30000$，$1\leq t\leq 3$，$1\leq W_i\leq 100$。