题目详情题解（0）讨论（0）提交记录（0）

AT_s8pc_1_g.Revenge of Traveling Salesman Problem

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

E869120 是一名推销员，为了完成任务，他需要经过所有的建筑物一次，然后返回到起点，也就是他的商店。

在他居住的城镇里，有 NN 个建筑物和 MM 条道路。建筑物从 1 开始编号，商店位于建筑物 1。

每一条道路 ii 连接了建筑物 sis_i 和 tit_i，其长度为 did_i。

值得注意的是，为了安全，该镇的某些道路会在一定时间后关闭。

具体来说，E869120 从商店出发后经过时间 timeitime_i，第 ii 条道路就会关闭。

因此，必须在关闭前通过这些道路。

E869120 想知道：在最短时间内回到商店的方法有多少种？

最短路径的长度以及以最短时间返回商店的方法总数需要由你来计算。假设 E869120 每单位时间可以移动一单位距离，并且所有道路都是双向通行的。

输入格式

输入为以下格式：

NN MM
s1s_1 t1t_1 d1d_1 time1time_1
s2s_2 t2t_2 d2d_2 time2time_2
...
sMs_M tMt_M dMd_M timeMtime_M

  • 第一行包含两个整数 NN 和 MM。
  • 接下来的 MM 行，每行由四个整数 si,ti,di,timeis_i, t_i, d_i, time_i 组成。

输出格式

输出包括：

  • 如果存在满足条件的路径，输出最短路径时间和方法总数，用空格隔开。
  • 如果不存在满足条件的路径，输出 "IMPOSSIBLE"。
  • 输出结果后加上换行符。

输入输出样例

  • 输入#1

    3 3
1 2 1 6
2 3 2 6
3 1 3 6

    输出#1

    6 2

  • 输入#2

    3 3
1 2 1 1
2 3 1 3
3 1 1 3

    输出#2

    3 1

  • 输入#3

    3 3
1 2 1 1
2 3 1 1
3 1 1 1

    输出#3

    IMPOSSIBLE

  • 输入#4

    3 2
1 2 3 20
2 3 2 20

    输出#4

    IMPOSSIBLE

说明/提示

  • 1≤N≤161 \leq N \leq 16
  • 1≤si<ti≤N1 \leq s_i < t_i \leq N
  • 1≤di≤10121 \leq d_i \leq 10^{12}
  • 1≤timei≤10121 \leq time_i \leq 10^{12}
  • 任意 i,ji,j 满足 (si,ti)≠(sj,tj)(s_i, t_i) \neq (s_j, t_j)

部分分数

  • 满足 2≤N≤82 \leq N \leq 8 的数据集全部正确，将得到 15 分。
  • 剩余数据集全部正确，将得到 85 分。

样例解释

  1. 如果路径是 1→2→3→11 \rightarrow 2 \rightarrow 3 \rightarrow 1 或 1→3→2→11 \rightarrow 3 \rightarrow 2 \rightarrow 1，都可以用 6 个单位时间完成，这是最短路径。

  2. 由于道路 1 在 1 单位时间后关闭，因此路径 1→3→2→11 \rightarrow 3 \rightarrow 2 \rightarrow 1 无法完成。

  3. 如果路径 1→2→3→11 \rightarrow 2 \rightarrow 3 \rightarrow 1 或 1→3→2→11 \rightarrow 3 \rightarrow 2 \rightarrow 1 都不可行，那么 E869120 无法完成任务。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页