問題文
E869120 是一名推销员。因此,他必须经过所有建筑物1每栋建筑物一次并返回商店。
E869120 居住的城市有N栋建筑,M条道路。建筑编号从 1 开始编号,商店位于建筑1。
,道路 i 连接建筑s_i和建筑t_i,距离为d_i。
但是,为了防范可疑人员,该城市在超过一定时间后会关闭道路。
道路 i在 E869120 出发后 time_i 时间,道路将被关闭。
因此,在通过该道路时,必须在 time_i 时间内完成通行。
那时,E869120 想到了如下问题:
“以最短时间返回的方法总共有多少?”
因此,作为优秀的程序员的你,需要编写一个程序。
请计算最短路径,以及以最短时间返回的方法总数。不过,E869120 每单位时间 1 前进距离 1 。另外,道路是双向通行的。
入力
输入是按以下格式从标准输入给出的。
N M s_1 t_1 d_1 time_1 s_2 t_2 d_2 time_2 :: : : s_M t_M d_M time_M
、第1行为整数N , M 。 表示
、接下来的M行中,为整数s_i , t_i , d_i , time_i
用空格分隔。
出力
应按以下格式输出到标准输出。 新道路建成后所有可能城市之间的最短路线长度之和,直至
输出最短路径和以最短时间返回的方法总数,用空格分隔。
如果不存在这样的路径,则输出"IMPOSSIBLE"。
此外,在输出末尾加上换行符。
制約
- 1≦N≦16
- 1≦s_i<t_i≦N ※输入示例中不一定如此
- 1≦d_i≦1,000,000,000,000
- 1≦time_i≦1,000,000,000,000
- 任何i,j, (s_i,t_i)≠(s_j,t_j)
部分点
2≦N≦8如果对满足条件的数据集全部正确,将获得15分。
如果对其余所有数据集全部正确,将获得85分。
入力例1
3 3 1 2 1 6 2 3 2 6 3 1 3 6
出力例1
6 2
1->2->3->1 或 至少 1->3->2->1 去往,则可以用时间6到达。这是最短路径。
入力例2
3 3 1 2 1 1 2 3 1 3 3 1 1 3
出力例2
3 1
道路1当时间1过去后将关闭, 1->3->2->1不能去往。
入力例3
3 3 1 2 1 1 2 3 1 1 3 1 1 1
出力例3
IMPOSSIBLE
1->2->3->1 , 1->3->2->1因为不能去往,因此E869120无法发挥作用。
入力例4
3 2 1 2 3 20 2 3 2 20
出力例4
IMPOSSIBLE