Poj 3411 Paid Roads (DFS 特殊标记方法)

╰+哭是因爲堅強的太久メ 2023-01-06 11:48 90阅读 0赞

挺有意思的一道搜索题

题意：有n座城市和m（1<=n，m<=10）条路。现在要从城市1到城市n。有些路是要收费的，从a城市到b城市，如果之前到过c城市，那么只要付P的钱，如果没有去过就付R的钱。求的是最少要花多少钱。

注意：路径是有向的。

以上描述参考了http://blog.csdn.net/lyy289065406/article/details/6689310

思路：数据规模很小，DFS即可，标记方法比较特殊

#include <cstdio>
    #include <cstring>
    
    const int INF=0x3fffffff;
    
    int n,m;
    int vist[11];  //记录城市的访问次数,每个城市最多经过3次
    int MinCost;  //最小总花费
    
    struct Node
    {
    	int a,b,c,p,r;
    	void Get ()
    	{
    		scanf("%d%d%d%d%d",&a,&b,&c,&p,&r);
    	}
    }road[11];
    
    void DFS (int a,int fee)   //a:当前所在城市,fee:当前方案的费用
    {
    	if (a==n && MinCost>fee)
    	{
    		MinCost=fee;
    		return;
    	}
    	for (int i=1;i<=m;i++)  //枚举道路
    		if (a==road[i].a && vist[ road[i].b ]<=3)
    		{
    			int b=road[i].b;
    			vist[b]++;
    
    			if (vist[ road[i].c ])
    				DFS(b,fee+road[i].p);
    			else
    				DFS(b,fee+road[i].r);
    
    			vist[b]--;       //回溯
    		}
    	return;
    }
    
    int main ()
    {
    	while (~scanf("%d%d",&n,&m))
    	{
    		memset(vist,0,sizeof(vist));
    		vist[1]=1; //从城市1出发
    		MinCost=INF;
    		for (int i=1;i<=m;i++)
    			road[i].Get();
    		DFS (1,0);
    		if (MinCost==INF)
    			printf("impossible\n");
    		else
    			printf("%d\n",MinCost);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，90人围观）

还没有评论，来说两句吧...

相关阅读

相关 Poj 3411 Paid Roads (DFS 特殊标记方法)

挺有意思的一道搜索题题意：有n座城市和m（1<=n，m<=10）条路。现在要从城市1到城市n。有些路是要收费的，从a城市到b城市，如果之前到过c城市，那么只要付P的钱，如果

╰+哭是因爲堅強的太久メ/ 2023年01月06日 11:48/ 0 赞/ 91 阅读

相关 Atomic 特殊标记类

前言 `JDK`提供了两个额外附加信息的`Atomic`帮助类,主要处理`ABA`类问题 1. `AtomicMarkableReference` 2. `Atom

左手的ㄟ右手/ 2022年12月19日 15:25/ 0 赞/ 102 阅读

相关 poj1947Rebuilding Roads（树形dp）

题目：[poj1949Rebuilding Roads][] 题意：给出一棵树，问现在要得到一颗有p个节点的子树，需要最少减掉几条边？分析：首先可以明确是一个树形

妖狐艹你老母/ 2022年08月08日 03:28/ 0 赞/ 159 阅读

相关 dfs+剪枝 poj1011

大致题意：给定一堆不定长度的小棒子，问他们能否构成一个正方形。思路：对所有的棒子求和sum之后除以4，得到边长side，问题就转换为求这些棒子能否拼接成4个长度为side的

小咪咪/ 2022年08月03日 16:54/ 0 赞/ 148 阅读

相关 POJ - 1251 - Jungle Roads

-------------------- 题目连接：[http://poj.org/problem?id=1251][http_poj.org_problem_id_1251

梦里梦外;/ 2022年06月10日 00:09/ 0 赞/ 136 阅读

相关 poj-1251--Jungle Roads

Jungle Roads <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS

浅浅的花香味﹌/ 2022年05月29日 03:11/ 0 赞/ 144 阅读

相关 POJ 3411 Paid Roads

[主题链接~~>][Link 1] 做题情绪：先前看过一次，感觉做多了状态压缩之后。再做这题就非常顺手了。解题思路： BFS + 状态压缩一个城市能够走多次，so ~

约定不等于承诺〃/ 2022年03月28日 08:30/ 0 赞/ 106 阅读

相关 POJ1251 Jungle Roads 题解

POJ1251 Jungle Roads 题解这道是最小生成树简单题，但是我还是认真的做了一个翻译工作:[POJ1251翻译][POJ1251] Prim:

小鱼儿/ 2021年12月13日 21:59/ 0 赞/ 162 阅读

相关 POJ 3050 Hopscotch——————dfs

[Hopscotch][] Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6738 Accep

雨点打透心脏的1/2处/ 2021年11月16日 16:31/ 0 赞/ 143 阅读

相关 DFS解决POJ 1979

Description There is a rectangular room, covered with square tiles. Each tile is

淡淡的烟草味﹌/ 2021年11月11日 11:50/ 0 赞/ 199 阅读