dijkstra第二标尺模板

dijkstra版

for(int v = 0; v < n; v++) {
  if(visit[v] == false && e[u][v] != inf) {
    if(dis[u] + e[u][v] < dis[v]) {
      dis[v] = dis[u] + e[u][v];
      w[v] = w[u] + weight[v];
    }else if(dis[u] + e[u][v] == dis[v] && w[u] + weight[v] > w[v]) {
      w[v] = w[u] + weight[v];
    }
  }
}

dijkstra+dfs版

void dfs(int v) {
    if(v == s) {
        temppath.push_back(v);
        int tempcost = 0;
        for(int i = temppath.size() - 1; i > 0; i--) {
            int id = temppath[i], nextid = temppath[i-1];
            tempcost += cost[id][nextid];
        }
        if(tempcost < mincost) {
            mincost = tempcost;
            path = temppath;
        }
        temppath.pop_back();
        return ;
    }
    temppath.push_back(v);
    for(int i = 0; i < pre[v].size(); i++)
        dfs(pre[v][i]);
    temppath.pop_back();
}

解释:

对于递归边界而言,如果当前访问的是叶子节点(路径的开始节点),那么说明到达了递归边界,把v压入tempath,tempath里面保存了一条完整路径。如果计算得到的当前的value大于最大值,就path=tempath。然后把tempath的最后一个结点弹出,return

对于递归式而言,每一次都是把当前访问的结点压入,然后找它的pre[v][i],进行递归,递归完毕弹出最后一个结点

(参考自柳神笔记)

上一篇:2I寒冰王座


下一篇:stack 相关