首页 > 代码库 > poj 1724ROADS（bfs和dfs做法）

poj 1724ROADS（bfs和dfs做法）

2024-07-14 12:22:18   222人阅读

 1 /* 2 dfs比较好想，就是测试数据的问题，导致在遍历边的时候要倒着遍历才过！ 3 */ 4 #include<iostream>  5 #include<cstdio> 6 #include<cstring> 7 #include<vector> 8 #include<algorithm> 9 #define Max 0x3f3f3f3f10 using namespace std;11 12 struct node{13    int D;14    int L, T;15    node(int D, int L, int T){16       this->D=D;17       this->L=L;18       this->T=T;19    }20    node(){21    }22 };23 24 node v[105][1000];25 int cnt[105];26 int vis[105];27 28 int maxCost, R, N, S, D, L, T;29 int cost, dist;30 31 void dfs(int cur, int d, int c){32    int i;33    if(cur == N){34        if(dist>d){35           dist=d;36           if(cost>c)  cost=c;37        }38        return ;39    }40    for(i=cnt[cur]-1; i>=0; --i)41       if(!vis[v[cur][i].D] &&  c+v[cur][i].T<=maxCost && d+v[cur][i].L<dist){42          vis[v[cur][i].D]=1;43          dfs(v[cur][i].D, d+v[cur][i].L, c+v[cur][i].T);44          vis[v[cur][i].D]=0;45       }46 }47 48 int main(){49    while(scanf("%d", &maxCost)!=EOF){50        scanf("%d%d", &N, &R);51        memset(cnt, 0, sizeof(cnt));52        while(R--){53           scanf("%d%d%d%d", &S, &D, &L, &T);54           v[S][cnt[S]++]=node(D, L, T);55        }56        cost=dist=Max;57        memset(vis, 0, sizeof(vis));58        dfs(1, 0, 0);59        if(cost<=maxCost)60           printf("%d\n", dist);61        else printf("-1\n");62    }63    return 0;64 }
 1 /* 2   spfa + 01背包  3   dist[next][j]=min(dist[cur][j-v[cur][i].T]+v[cur][i].L) j={v[cur][i].T。。。maxCost} 4   一维数组表示的是城市节点，二维表示的当前费用 5   dist[i][j]表示经过i城市，费用为j时总的路径长度！  6 */ 7 #include<iostream>  8 #include<cstdio> 9 #include<cstring>10 #include<vector>11 #include<queue>12 #include<algorithm>13 #define Max 0x3f3f3f3f14 using namespace std;15 16 struct node{17    int D;18    int L, T;19    node(int D, int L, int T){20       this->D=D;21       this->L=L;22       this->T=T;23    }24    node(){25    }26 };27 28 node v[105][1000];29 int cnt[105];30 int dist[105][10005];31 int vis[105];32 queue<int>q;33 int maxCost, R, N, S, D, L, T;34 35 int spfa(){36    int i;37    while(!q.empty()){38        int cur = q.front();39        q.pop();40        vis[cur]=0;41        for(i=0; i<cnt[cur]; ++i){42            int next=v[cur][i].D;43            for(int j=v[cur][i].T; j<=maxCost; ++j)44               if(dist[next][j]>dist[cur][j-v[cur][i].T]+v[cur][i].L){45                  dist[next][j]=dist[cur][j-v[cur][i].T]+v[cur][i].L;46                  if(!vis[next]){47                    vis[next]=1;48                    q.push(next);49                  }50              }51        }52    }53 }54 55 void bfs(int cur){56    q.push(1);57    memset(dist, 0x3f, sizeof(dist));58    for(int i=0; i<105; ++i)59       dist[1][i]=0;60    vis[1]=1;61    spfa();62 }63 64 int main(){65    while(scanf("%d", &maxCost)!=EOF){66        scanf("%d%d", &N, &R);67        memset(cnt, 0, sizeof(cnt));68        while(R--){69           scanf("%d%d%d%d", &S, &D, &L, &T);70           v[S][cnt[S]++]=node(D, L, T);71        }72        memset(vis, 0, sizeof(vis));73        bfs(1);74        int minDist=Max;75        for(int i=1; i<=maxCost; ++i)76           if(minDist>dist[N][i])77               minDist=dist[N][i];78        if(minDist!=Max)79           printf("%d\n", minDist);80        else printf("-1\n");81    }82    return 0;83 }

 

 

 


联系
我们