【NOIP模拟赛】长途旅行

2014年11月3日2,3333

【题目描述】

JY是一个爱旅游的探险家,也是一名强迫症患者。现在JY想要在C国进行一次长途旅行,C国拥有n个城市(编号为0,1,2…,n – 1),城市之间有m条道路,可能某个城市到自己有一条道路,也有可能两个城市之间有多条道路,通过每条道路都要花费一些时间。JY从0号城市开始出发,目的地为n – 1号城市。由于JY想要好好参观一下C国,所以JY想要旅行恰好T小时。为了让自己的旅行更有意思,JY决定不在任何一个时刻停留(走一条到城市自己的路并不算停留)。JY想知道是否能够花恰好T小时到达n – 1号城市(每个城市可经过多次)。现在这个问题交给了你。

若可以恰好到达输出“Possible”否则输出“Impossible”。(不含引号)。

 

【输入格式】

第一行一个正整数Case,表示数据组数。

每组数据第一行3个整数,分别为n, m, T。

接下来m行,每行3个整数x, y, z,代表城市x和城市y之间有一条耗时为z的双向边。

 

【输出格式】

对于每组数据输出”Possible”或者”Impossible”.

 

【样例输入】

2

3 3 11

0 2 7

0 1 6

1 2 5

2 1 10000

1 0 1

 

【样例输出】

Possible

Impossible

 

【样例解释】

第一组:0 -> 1 -> 2 :11

第二组:显然偶数时间都是不可能的。

 

【数据范围】

30%: T <= 10000

另有30%: n <= 5 , m <= 10.

100%: 2 <= n <= 50 , 1 <= m <= 100 , 1 <= z <= 10000 , 1 <= T <= 10^18 , Case <= 5.

题解

对于30%的数据

f[i][j]表示到i的路径长为j是否存在路径,然后直接spfa

考虑起点的某条出边,长度为d

则若1到n存在路径长度为D,且D+2kd=T

则possible

所以f[i][j]表示到i,j+2kd的最短路,最后判断f[n][T mod 2d]是否小于T

 

  • 间谍卫星5爱2015年11月4日 下午5:57 回复

    黄学长,问一下为什么任取一个环判断就可以了啊。能证明吗?
    (Ps.我猜黄学长肯定不记得我是谁了)

    #1  
  • 小蒟蒻2015年11月22日 下午8:53 回复

    黄学长,请问为什么任取一条起点的出边就行?难道不可以答案的方案是在某条1到n的路径上的结点对(i,j)(i,j != 1)之间的边走k次,其他的只走一次吗?

    #2  
    • hzwer2015年11月22日 下午9:02 回复
      admin

      因为这题的T很大,所以要对路径长度进行分类,我们发现,任取一条长为d的出边,模2d意义下的路径长度都是合法的。
      至于这些路径走不走环无所谓,但是处理后能保证你在某个环上绕的次数不超过2d,这样保证复杂度

      #21