首页 > 代码库 > POJ 3411 Paid Roads（DFS）
POJ 3411 Paid Roads（DFS）
【题目链接】 http://poj.org/problem?id=3411
【题目大意】
从a到b的路，如果已经访问过c那么路费为p否则为r，问从1到n的最短路
【题解】
搜索记录每个点在该回溯中被访问的次数，
因为这张图最多只有十个点，所以如果一个点被访问的次数超过3，
那么一定是重复走环路了，可证明重复走环路答案一定不是最优的因此可以停止继续搜索这个点。
【代码】
#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int INF=0x3f3f3f3f;int n,m,vis[20],ans;struct data{int a,b,c,p,r;}u[20];void dfs(int a,int w){ if(a==n&&ans>w){ans=w;return;} for(int i=1;i<=m;i++){ if(a==u[i].a&&vis[u[i].b]<=3){ int b=u[i].b; vis[b]++; if(vis[u[i].c])dfs(b,w+u[i].p); else dfs(b,w+u[i].r); vis[b]--; } }return;}int main(){ while(~scanf("%d%d",&n,&m)){ memset(vis,0,sizeof(vis)); vis[1]=1; ans=INF; for(int i=1;i<=m;i++)scanf("%d%d%d%d%d",&u[i].a,&u[i].b,&u[i].c,&u[i].p,&u[i].r); dfs(1,0); if(ans==INF)puts("impossible"); else printf("%d\n",ans); }return 0;}POJ 3411 Paid Roads（DFS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。