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],进行递归,递归完毕弹出最后一个结点

推荐这些文章:

树的路径模板

树的直径是求一棵树最远的两点之间的距离。
套路:两次dfs,一次dfs求离根最远的结点A,再以A为根搜索离A最远的结点B,A到B就是树的直径(双向的树)
#include<bits/stdc++.h>
using namespace std;
const int N=100010;

int n;
struct node{
int idx,value; //value: distance from this to idx
};
vector<node> h[N];
int dis[N];

void dfs(int u,int f,int distance){...

【代码模板】图论

图的存储
树是一种特殊的图,与图的存储方式相同。
对于无向图中的边ab,存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。
(1) 邻接矩阵:g[a][b] 存储边a->b
(2) 邻接表:
// 对于每个点k,开一个单链表,存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
me...

dfs全排列问题模板

https://www.acwing.com/problem/content/description/1211/
全排列问题+如何利用全排列插入符号来计算
#include <bits/stdc++.h>
using namespace std;
const int N=10;
int dist[N];
int mark[N];
int target,cnt;

int cal(int l,int r){
int res=0;
for(int i=l;i<=r;i++){
res=res*10+dist[i];
}
retur...

两点间最短路模板Dijkstra

struct node{
int ne,v;
node(int _n,int _v):ne(_n),v(_v){}
};
vector<struct node> edge[n];#构造图
for(int i=0;i<e.size();i++){
int x=e[i][0];
int y=e[i][1];
int z=e[i][2];
edge[x].emplace_back(node(y,z));
}

int vis[n];
int d[n];
function&l...

Dijkstra【模板】【邻接表+优先队列】

时间复杂度:O((n+m)logm)
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define MP make_pair
const int N=100010,M=200010;
const int inf=0x7fffffff;

int fr[N],nex[M],dis[N];//邻接表结点数组和距离数组,dis[i]表示源点到i点距离。
int v[M],w[M];//顶点数组和边长数组
bool vis[N];//标记数组
int n,m...

【数据结构与算法】图的模板及例题

图的存储结构

邻接矩阵
适用于边数较多的情况,采用二维数组存储
// 邻接矩阵数组:w[from][to] = weight 代表从 from 到 to 有权重为 weight 的边
int[][] w = new int[N][N];

// 加边操作
void add(int from, int to, int weight) {
w[from][to] = weight;
}

邻接表(链式前向星存图)
数组加单链表(头插法)
适用于边数较少的情况
数组模拟链表
int[] he = new int[N], e = new int[M], ne = new int[M], ...

P3371 【模板】单源最短路径(弱化版)

 
题目链接 https://www.luogu.com.cn/problem/P3371
几种方法慢慢更

 
Dijkstra
放AC代码

1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,m,s;
4 int a,b,c;
5 int cnt;
6 int head[20010];
7 bool vis[20010];
8 long long dis[20010];
9
10 struct edge
11 {
12 int v;
13 int ...

常用算法模板总结c++DFS&BFS

深度优先遍历

int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过

for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}

宽度优先遍历

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
int t = q.front();
q.pop()...

35.图

1.定义变量
private ArrayList<String> vertexList; //存储顶点集合
private int[][] edges; //存储图对应的邻结矩阵
private int numOfEdges; //表示边的数目
//定义给数组boolean[], 记录某个结点是否被访问
private boolean[] isVisited;
 
2.构造器
public Graph(int n) {
//初始化矩阵和vertexList
edges = new int[n][n];
vertexList = new ArrayLis...

【力扣每日打卡】2022.2.24球会落入何处

今天开始每天打卡了!

 
 题目如上
一开始也没啥好思路,就是想着暴力解,遍历一下 每个小球的下落路径就行,区分一下情况。
后来还是看了题解再做
觉得dfs是不错的方法,采用了递归的方式
首先要区分清楚不同的情况,找到递归的出口
然后再找到递归关系即可了。
以后这种思路要有的。

class Solution {
private:
int m,n;
public:

vector<int> findBall(vector<vector<int>>& grid) {
m=grid.size...

文章标题:dijkstra第二标尺模板
文章链接:https://www.dianjilingqu.com/51007.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>