dij免费问题

今天打预选赛遇到了一题dij，但并不是普通的dij，他还要求其中有一段a-b是可以免费的，让你求最小车费。先梳理一下普通dij的思路，vis记录路径是否走过，g记录点与点之间的联通关系以及可以记录点与点之间的权值，ans记录答案，然后还有一个主体需要维护的优先队列，小顶堆排序

，将每个还没走过的点放进队列，等待走，并以此访问他的邻居。更新原则是从起点到当前走到的点和起点到当前点的邻居比较，取较小的那个。而这题多了一个可以买南非的条件，也就是其中一条边你可以让他权值为0，当然，那条边权值为0总价值最小，这个也需要遍历访问处理，如果其中有一段为零，相当于再一条完整的线剪上一刀，那么就会分成两段了，，那就需要两个数组分别记录作为不同起点时的最小价值，因为中间会空上一段a-b，那么就会分成1-a，b-n，，那么你就需要两个数组来得到这两个的值，那么我就想过那我用一个数组，分别设置不同的起点来算可以吗，不行这样后面会覆盖前面的结果，如果你那一个数组先算从1-a，记录为tmp1，再算1-b，tmp2，再算1-n，记为tmp3，最后tmp1+tmp3-tmp2并不是最短的，因为就你那是单独的最小值，并不是连续的最小值，我从b-n的最小值并不一定是tmp3-tmp2。最后那一步的时候先a再b和先b再a是不一样的，虽然这里是无向图，在无向图中不管是a-b还是b-a权值都一样，但这里要表达的意思是先a在b还是先b在a他们走过的节点是会不同的，那么权值和也就会不同。嗯，其实多出的东西就是这些