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<queue>

int dist[105][10005];

queue<int>q;

int spfa(){

   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();

       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);

本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3874165.html，如需转载请自行联系原作者