一共有T组数据,每组数据给定一张有n个点,m条边的无向图,点i的类型为typei,其中type1要么为1,要么为2。一个人想从s走到t,如果他经过的点i中typei=1,则p1++,否则p2++。求出在任何时候,|p1−p2|≤k,为条件下的最短路径。(有点牵强,理解就好)
Data Range:T≤10,n≤104,m≤105,k≤10
链接
题解
去搞生地会考了,所以近一个月没有更博客。(这就是理由??)
设可乐的权值为−1,汉堡的权值为1,喝掉的可乐的数量减去吃掉的汉堡的数量为p。
由于k≤10,所以可以考虑将一个点i拆成2k+1个点i−k,i−k+1,⋯,i−1,i0,⋯,ik,这里,il是指到达i且p=l时的最短路总长。
加边的话就这么做:(这里假设现在加的边是(i,j))
如果j卖汉堡的话,就从il连到jl−1,其中i−k不要连边,就像这样:
如果j卖可乐的话,就从il连到jl+1,其中ik不要连边。
但是,这是个无向图啊,按照上面的连边方式,连出来的是个有向图,而这题的边又不对称。
所以说,在加边(i,j)时,按照上面的方法先加一条边,在把i,j换一下,就行了。
于是在新的图上跑一遍最短路就做完了。
但是,这里有一些地方需要注意:
首先是起点的问题,这个应该不用多说,在起点或终点也要买可乐或汉堡。
然后是终点的问题,答案是终点拆出来的每一个点的最短路的最小值。
最后,要特判k=0的情况!!!
最最最后,多组数据,记得清零!!!
代码
1 |
|
v1.5.2