求助新定义最短路径问题
acm吧
全部回复
仅看楼主
level 3
qxyl 楼主
有没有大佬给点思路
2023年12月15日 06点12分 1
level 4
请不要这样，先生
数据范围呢[怒][怒][怒]
2023年12月15日 20点12分 2
qxyl
无
2023年12月17日 07点12分
level 4
请不要这样，先生
我会了，问题可以转化成跑最短路的过程中需要把一条边边权设置成0，一条边边权乘2，因为跑最短路，所以最后跑完一定是经过的边权最大的那条边设置成0了，最小的那条边边权被乘2，所以最后直接跑分层图最短路就好了
2023年12月17日 11点12分 3
qxyl
ok谢谢了 我去看看分层图最短路
2023年12月18日 07点12分
qxyl
哥 再问问你 最大边为0我会了 最小边走两次怎么用分层图处理啊？
2023年12月18日 09点12分
level 3
qxyl 楼主
@请不要这样，先生 是这样吗兄弟
2023年12月18日 09点12分 4
请不要这样，先生
应该是，感觉差不多，但要我写的话，直接开一个dis[2][2][N]的数组，第一维0/1代表有没有做边权变0那一步，第二维0/1代表有没有做边权乘2的那一步，然后直接跑最短路，dis[1][1][n]就是答案
2023年12月18日 10点12分
qxyl
@请不要这样，先生 ok谢谢了兄弟
2023年12月18日 11点12分
1