poj 1724ROADS(bfs和dfs做法)

简介:

/*
dfs比较好想,就是测试数据的问题,导致在遍历边的时候要倒着遍历才过!
*/
#include<iostream> 
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define Max 0x3f3f3f3f
using namespace std;

struct node{
   int D;
   int L, T;
   node(int D, int L, int T){
      this->D=D;
      this->L=L;
      this->T=T;
   }
   node(){
   }
};

node v[105][1000];
int cnt[105];
int vis[105];

int maxCost, R, N, S, D, L, T;
int cost, dist;

void dfs(int cur, int d, int c){
   int i;
   if(cur == N){
       if(dist>d){
          dist=d;
          if(cost>c)  cost=c;
       }
       return ;
   }
   for(i=cnt[cur]-1; i>=0; --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, &R);
       memset(cnt, 0, sizeof(cnt));
       while(R--){
          scanf("%d%d%d%d", &S, &D, &L, &T);
          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->D=D;
      this->L=L;
      this->T=T;
   }
   node(){
   }
};

node v[105][1000];
int cnt[105];
int dist[105][10005];
int vis[105];
queue<int>q;
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<105; ++i)
      dist[1][i]=0;
   vis[1]=1;
   spfa();
}

int main(){
   while(scanf("%d", &maxCost)!=EOF){
       scanf("%d%d", &N, &R);
       memset(cnt, 0, sizeof(cnt));
       while(R--){
          scanf("%d%d%d%d", &S, &D, &L, &T);
          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;
}

目录
相关文章
华为机试HJ44:Sudoku(数独问题,深度优先遍历DFS解法)
华为机试HJ44:Sudoku(数独问题,深度优先遍历DFS解法)
140 0
|
7月前
【每日一题Day295】LC617合并二叉树 | DFS BFS
【每日一题Day295】LC617合并二叉树 | DFS BFS
25 0
|
7月前
|
存储 人工智能 BI
【每日一题Day216】LC1377 T 秒后青蛙的位置 | BFS DFS
【每日一题Day216】LC1377 T 秒后青蛙的位置 | BFS DFS
54 0
|
存储 容器
华为机试HJ41:称砝码(深度优先遍历dfs-Depth First Search)
华为机试HJ41:称砝码(深度优先遍历dfs-Depth First Search)
150 0
UVa302 - John's trip(并查集、欧拉回路、DFS)
UVa302 - John's trip(并查集、欧拉回路、DFS)
53 0
|
算法
【和zqy学算法】Day1:DFS与BFS
【和zqy学算法】Day1:DFS与BFS
152 0
|
算法 Java 索引
【算法题解】 Day10 BFS | DFS
今天的算法是 「BFS | DFS」 相关,“算法题解系列文章旨在精选重点与易错的算法题,总结常见的算法思路与可能出现的错误,以实战习题的形式理解算法,使用算法。”
104 0
|
算法 Java Python
【算法题解】 Day6 BFS | DFS
今天的算法是 「BFS | DFS」 相关,“算法题解系列文章旨在精选重点与易错的算法题,总结常见的算法思路与可能出现的错误,以实战习题的形式理解算法,使用算法。”
103 0
|
定位技术
UPC——帕琪的药园(dfs或并查集)
UPC——帕琪的药园(dfs或并查集)
81 0
|
数据采集 算法 容器
一文带你了解dfs和bfs算法
dfs算法又称深度优先搜索,是计算机术语。 1、dfs是一种在开发爬虫早期使用较多的方法,是搜索算法的一种。 2、dfs的目的是要达到被搜索结构的叶结点,即那些不包含任何超链的HTML文件。 3、dfs根据已有的邻接矩阵或邻接表用递归方法编写深度优先搜索遍历算法,并输出遍历结果 作为搜索算法的一种,DFS对于寻找一个解的NP(包括NPC)问题作用很大。但是,搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法,它的效率非常低,在数据规模变大时,这种算法就显得力不从心了。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止
400 0
一文带你了解dfs和bfs算法