uva208
2024-09-21 02:46:06
一道简单的路径打印,首先需要一次dfs判断能否从1到达目标点,否则可能会超时。还有一点就是那个格式需要注意下,每条路径前没有空格(看起来好像有3个空格)….
AC代码:
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=21+5;
int vis[maxn];
vector<int>G[maxn];
int cnt=0,goal;
void reach(int u){ //能否到达目标节点
vis[u]=1;
int len=G[u].size();
for(int i=0;i<len;++i){
if(G[u][i]==goal) {vis[goal]=1;return;}
if(!vis[G[u][i]]) reach(G[u][i]);
}
}
void dfs(int *a,int cur,int u){
if(u==goal){
cnt++;
//printf(" ");
for(int i=0;i<cur;++i){
if(i==0) printf("%d",a[i]);
else printf(" %d",a[i]);
}
printf("\n");
return;
}
int len=G[u].size();
for(int i=0;i<len;++i){
if(!vis[G[u][i]]){
vis[G[u][i]]=1;
a[cur]=G[u][i];
dfs(a,cur+1,G[u][i]);
vis[G[u][i]]=0;
}
}
}
void solve(){
memset(vis,0,sizeof(vis));
reach(1);
if(!vis[goal]) return; //从1无法到达目标节点
memset(vis,0,sizeof(vis));
for(int i=1;i<maxn;++i){
sort(G[i].begin(),G[i].end()); //排序的目的是方便按字典序输出
}
int a[maxn];
a[0]=1; //1作为起点
vis[1]=1;
dfs(a,1,1);
}
int main(){
int kase=0;
while(scanf("%d",&goal)==1){
cnt=0;
int x,y;
while(scanf("%d%d",&x,&y)==2&&x){
G[x].push_back(y);
G[y].push_back(x);
}
printf("CASE %d:\n",++kase);
solve();
printf("There are %d routes from the firestation to streetcorner %d.\n",cnt,goal);
for(int i=0;i<maxn;++i) G[i].clear();
}
return 0;
}
如有不当之处欢迎指出!
最新文章
- UIViewController 生命周期
- Android开发自学笔记(Android Studio)—4.3ImageView及其子类
- Sokcet方式请求HTTP/HTTPS的封装类HttpHelper
- SQL INSERT INTO 语句
- c语言计算矩阵特征值和特征向量-1(幂法)
- 【BZOJ-1324】Exca王者之剑 最小割
- 【总结】String in Java
- Understanding Asynchronous IO With Python 3.4&#39;s Asyncio And Node.js
- grant授权“失败”的原因
- 微调Win8.1这台电脑
- (转)iOS7界面设计规范(5) - UI基础 - 导航
- Git 配置editor编辑器
- java对象深复制、浅复制(深拷贝、浅拷贝)的理解
- OAuth2.0记录
- python爬虫,爬取一系列新闻
- c#线程池中的异常
- W3bsafe]SQLmap过狗命令的利用+教程
- 单元测试系列之七:Sonar 数据库表关系整理一(rule相关)
- MyBatis是如何解决Sql注入的
- EDK II之USB总线驱动的实现框架