首页 > 代码库 > poj 3411 Paid Roads (dfs)

poj 3411 Paid Roads (dfs)

2024-07-14 01:25:22   244人阅读

题目链接

题意：有N个城市被M条道路连接起来了，每两个城市之间可能存在超过一条路，但是城市之间是单向连接的。

每条路是要花费的。每条路的花费可以选择两种方式：1：假如a城市到达b城市，如果之前经过了c城市，那么这条

路上的花费为P也可以为R。2：如果没有经过c，则这条路上的花费为R。问从城市1到城市n最小的花费是多少.

思路：存在走多次边的情况，所以vis[]数组可以多次，但是这个题目的多次的上限为3（不知道为什么）。

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstdio> 6 #include <vector> 7 #include <algorithm> 8 #define LL long long 9 using namespace std;10 const int maxn = 20+10;11 const int INF = 1<<28;12 int n, m, vis[maxn], ans;13 struct node14 {15     int b, c, p, r;16 }tmp;17 vector<node>v[maxn];18 19 void dfs(int x, int cost)20 {21     vis[x] ++;22     if(cost >= ans) return;23     if(x == n)24     {25         ans = cost;26         return;27     }28     int t, b1;29     for(int i = 0; i < v[x].size(); i++)30     {31         b1 = v[x][i].b;32         if(vis[b1]<=3)33         {34             t = INF;35             if(vis[v[x][i].c])36             t = v[x][i].p;37             if(t > v[x][i].r)38             t = v[x][i].r;39             dfs(b1, cost+t);40             vis[b1] --;41         }42     }43 }44 int main()45 {46     int i;47     int a1, b1, c1, p1, r1;48     while(~scanf("%d%d", &n, &m))49     {50         ans = INF;51         memset(vis, 0, sizeof(vis));52         for(i = 0; i < m; i++)53         {54           cin>>a1>>b1>>c1>>p1>>r1;55           tmp.b = b1; tmp.c = c1;56           tmp.p = p1; tmp.r = r1;57           v[a1].push_back(tmp);58         }59         dfs(1, 0);60         if(ans == INF) cout<<"impossible"<<endl;61         else cout<<ans<<endl;62     }63     return 0;64 }

 


联系
我们