思路是分层图
by Frederick123 @ 2022-12-18 12:32:26
我用dij过了
by Cerisier @ 2022-12-18 12:50:01
但是做法不同,你看看是不是可能生成了负权边,你输出一下图试试,dij 跑不了负权边
by Cerisier @ 2022-12-18 12:50:59
```cpp
for(int i=1;i<=n;i++)
add(i,i+n,price[i]);
for(int i=1;i<=n;i++)
add(i+n,i+n+n,-price[i]);
```
找到了,一定会产生负权边,dij 会挂
by Cerisier @ 2022-12-18 12:51:22
哦,谢谢!
by Frederick123 @ 2022-12-18 13:51:00
@[Cerisier](/user/670262)
by Frederick123 @ 2022-12-18 16:08:07
此贴完结
by Frederick123 @ 2022-12-18 16:08:27