poj 1724ROADS（bfs和dfs做法）

for(i=cnt[cur]-1; i --i) if(!vis[v[cur][i].D] c+v[cur][i].T =maxCost d+v[cur][i].L dist){ vis[v[cur][i].D]=1; dfs(v[cur][i].D, d+v[cur][i].L, c+v[cur][i].T); vis[v[cur][i].D]=0; int main(){ while(scanf("%d", maxCost)!=EOF){ scanf("%d%d", N, memset(cnt, 0, sizeof(cnt)); while(R--){ scanf("%d%d%d%d", S, D, L, v[S][cnt[S]++]=node(D, L, T); cost=dist=Max; memset(vis, 0, sizeof(vis)); dfs(1, 0, 0); if(cost =maxCost) printf("%d\n", dist); else printf("-1\n"); return 0; spfa + 01背包 dist[next][j]=min(dist[cur][j-v[cur][i].T]+v[cur][i].L) j={v[cur][i].T。。。maxCost} 一维数组表示的是城市节点，二维表示的当前费用 dist[i][j]表示经过i城市，费用为j时总的路径长度！ #include iostream #include cstdio #include cstring #include vector #include queue #include algorithm #define Max 0x3f3f3f3f using namespace std; struct node{ int D; int L, T; node(int D, int L, int T){ this- this- this- node(){ node v[105][1000]; int cnt[105]; int dist[105][10005]; int vis[105]; queue int int maxCost, R, N, S, D, L, T; int spfa(){ int i; while(!q.empty()){ int cur = q.front(); q.pop(); vis[cur]=0; for(i=0; i cnt[cur]; ++i){ int next=v[cur][i].D; for(int j=v[cur][i].T; j =maxCost; ++j) if(dist[next][j] dist[cur][j-v[cur][i].T]+v[cur][i].L){ dist[next][j]=dist[cur][j-v[cur][i].T]+v[cur][i].L; if(!vis[next]){ vis[next]=1; q.push(next); void bfs(int cur){ q.push(1); memset(dist, 0x3f, sizeof(dist)); for(int i=0; i ++i) dist[1][i]=0; vis[1]=1; spfa(); int main(){ while(scanf("%d", maxCost)!=EOF){ scanf("%d%d", N, memset(cnt, 0, sizeof(cnt)); while(R--){ scanf("%d%d%d%d", S, D, L, v[S][cnt[S]++]=node(D, L, T); memset(vis, 0, sizeof(vis)); bfs(1); int minDist=Max; for(int i=1; i =maxCost; ++i) if(minDist dist[N][i]) minDist=dist[N][i]; if(minDist!=Max) printf("%d\n", minDist); else printf("-1\n"); return 0; }
【算法题解】 Day10 BFS | DFS 今天的算法是 「BFS | DFS」 相关，“算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，以实战习题的形式理解算法，使用算法。”
【算法题解】 Day6 BFS | DFS 今天的算法是 「BFS | DFS」 相关，“算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，以实战习题的形式理解算法，使用算法。”
一文带你了解dfs和bfs算法 dfs算法又称深度优先搜索，是计算机术语。 1、dfs是一种在开发爬虫早期使用较多的方法，是搜索算法的一种。 2、dfs的目的是要达到被搜索结构的叶结点，即那些不包含任何超链的HTML文件。 3、dfs根据已有的邻接矩阵或邻接表用递归方法编写深度优先搜索遍历算法，并输出遍历结果 作为搜索算法的一种，DFS对于寻找一个解的NP（包括NPC）问题作用很大。但是，搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率非常低，在数据规模变大时，这种算法就显得力不从心了。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止
[Nowcoder] network | Tarjan 边双连通分量 | 缩点 | LCA倍增优化 | 并查集 题目描述 A network administrator manages a large network. The network consists of N computers and M links between pairs of computers. Any pair of computers are connected directly or indirectly by successive links, so data can be transformed between any two computers.