题意:有n座城市和m(1
解题思路:这道题的n与m都很小,dfs可以搞定,但这里与以往的搜索不同,以前dfs每个节点只能够访问一次,这里有多次访问的可能性。很好的是这道题给的是一个有向图,我们只要知道某节点被访问的次数即可,如果访问次数过多,那么肯定是走到了一个环,立即跳出来。。参考了别人的,节点访问次数最多只有3
AC:
#include
#include
#include
using namespace std;
const int inf = 0x3f3f3f;
struct Edge
{
int k,c,p,r,next;
}edge[20];
int n,m,cnt,vis[20],pre[20],ans;
void addedge(int a,int b,int c,int p,int r)
{
edge[cnt].k = b;
edge[cnt].c = c;
edge[cnt].p = p;
edge[cnt].r = r;
edge[cnt].next = pre[a];
pre[a] = cnt++;
}
void dfs(int cur,int sum)
{
if(cur == n)
{
if(ans > sum) ans = sum;
return;
}
if(vis[cur] > 3 || sum > ans) return;
vis[cur]++;
for(int i = pre[cur]; i != -1; i = edge[i].next)
{
int k = edge[i].k;
if(vis[edge[i].c])
dfs(k,sum+edge[i].p);
else dfs(k,sum+edge[i].r);
}
vis[cur]--;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
cnt = 0;
memset(pre,-1,sizeof(pre));
memset(vis,0,sizeof(vis));
for(int i = 1; i
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: 数据治理之关键环节元数据管理开源项目datahub探索
@ 目录 概述 定义 核心功能 概念 元数据应用 其他开源 架构 概览 组件 元数据摄取架构 服务体系结构 本地部署 环境要求 安装 摄取样例 摄取入门 介绍 核心概念 命令行MySQL摄取示例 配置ClickHouse摄取示例 概述 定义 datahub 官…