← 返回题目列表

AtCoder · s8pc_1_g

G. 旅行商复仇问题

中文机器翻译题面 查看原题

問題文

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