与Dijkstra大战两个回合

北美求职 转码 近期找工作现状 LeetCode 每天59秒拿下每日一题 创作灵感 国区每日一题今日思路： 数字频率。统计每一个数位对应数字的出现频率，每个数字对总和的贡献为除当前数字外，该数位上所有数字频率和。这里可以额外维护一个总和数组，用于计算剔除当前数字的总和。 国际站每日一题今日思路： 首先把所有-1的边变成1，如果最小的更改方式无法满足，直接返回空集。记路径s-x-y-d，s表示起点，x和y表示要修改的一条-1边的端点，d表示终点，有如下式子：target=d2(s,x) + w + d1(y,d) 第一项用第二次跑的路径，第二项为需更改的值，第三项可以直接使用第一次跑路径的结果(前提是y必须在最短路径路由中)，借助第一次跑的路径，相当于知道路由，上式变为target=d(s,x) + w + d(s,d) – d(s, y) 转换一下 w=target-d1(s,d)+d1(s,y)-d2(s,x)。这样在修改路径时，可以省去再跑一次Dijkstra。如果第二次跑完仍然存在小于target的路径，也返回空集。最后处理未被访问的边，将其任意赋值即可。看到这点个赞吧[喝奶茶R]