hdu 1142 A Walk Through the Forest

时间:2021-01-02 01:24:25

http://acm.hdu.edu.cn/showproblem.php?pid=1142

这道题是spfa求最短路,然后dfs()求路径数。

 #include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define maxn 1001
using namespace std;
const int inf=<<; int g[maxn][maxn];
int dis[maxn];
bool vis[maxn],visi[maxn];
int n,m,a,b,d;
int di;
int cnt[maxn];
int num[maxn]; bool spfa()
{
queue<int>q;
memset(vis,false,sizeof(vis));
memset(cnt,,sizeof(cnt));
for(int i=; i<=n; i++) dis[i]=inf;
dis[]=;
vis[]=true;
q.push();
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=false;
for(int i=; i<=n; i++)
{
if(dis[i]>dis[u]+g[u][i]&&g[u][i]!=inf)
{
dis[i]=dis[u]+g[u][i];
if((++cnt[i])>n) return false;
if(!vis[i])
{
q.push(i);
vis[i]=true;
}
}
}
}
return true;
} void dfs(int src)
{
if(src==)
{
num[]=;
return ;
}
int sum=;
for(int i=; i<=n; i++)
{
if(g[src][i]!=inf&&dis[src]>dis[i])
{
if(num[i]>=)
{
sum+=num[i];
}
else
{
dfs(i);
sum+=num[i];
}
}
}
num[src]=sum;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(n==) break;
scanf("%d",&m);
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
if(i==j) g[i][j]=;
else g[i][j]=inf;
}
}
for(int i=; i<m; i++)
{
scanf("%d%d%d",&a,&b,&d);
g[a][b]=g[b][a]=min(g[a][b],d);
}
spfa();
//printf("%d\n",dis[1]);
for(int i=; i<=n; i++)
{
num[i]=-;
}
dfs();
printf("%d\n",num[]);
}
return ;
}

hdu 1142 A Walk Through the Forest的更多相关文章

  1. HDU 1142 A Walk Through the Forest &lpar;记忆化搜索 最短路&rpar;

    A Walk Through the Forest Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Jav ...

  2. HDU 1142 A Walk Through the Forest (求最短路条数)

    A Walk Through the Forest 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1142 Description Jimmy exp ...

  3. HDU 1142 A Walk Through the Forest(最短路&plus;记忆化搜索)

    A Walk Through the Forest Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Jav ...

  4. hdu 1142 A Walk Through the Forest &lpar;最短路径&rpar;

    A Walk Through the Forest Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Jav ...

  5. 题解报告:hdu 1142 A Walk Through the Forest

    题目链接:acm.hdu.edu.cn/showproblem.php?pid=1142 Problem Description Jimmy experiences a lot of stress a ...

  6. HDU 1142 A Walk Through the Forest(最短路&plus;dfs搜索)

    A Walk Through the Forest Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Jav ...

  7. 【解题报告】HDU -1142 A Walk Through the Forest

    原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=1142 题目大意:Jimmy要从办公室走路回家,办公室在森林的一侧,家在另一侧,他每天要采取不一样的路线 ...

  8. HDU 1142 A Walk Through the Forest(SPFA&plus;记忆化搜索DFS)

    题目链接 题意 :办公室编号为1,家编号为2,问从办公室到家有多少条路径,当然路径要短,从A走到B的条件是,A到家比B到家要远,所以可以从A走向B . 思路 : 先以终点为起点求最短路,然后记忆化搜索 ...

  9. HDU 1142 A Walk Through the Forest&lpar;dijkstra&plus;记忆化DFS&rpar;

    题意: 给你一个图,找最短路.但是有个非一般的的条件:如果a,b之间有路,且你选择要走这条路,那么必须保证a到终点的所有路都小于b到终点的一条路.问满足这样的路径条数 有多少,噶呜~~题意是搜了解题报 ...

随机推荐

  1. MVC - 学习总目录

    MVC - 基础 MVC - HtmlHelper类 MVC - 路由 MVC - 身份验证 MVC - 模型验证 MVC - Ajax MVC - 布局

  2. hdu5391 Zball in Tina Town&lpar;威尔逊定理&rpar;

    转载请注明出处: http://www.cnblogs.com/fraud/          ——by fraud Zball in Tina Town Time Limit: 3000/1500 ...

  3. ubuntu下lamp环境配置及将window代码迁移至linux系统

    因为最近要用需要去实现项目中的一个功能,比较好的做法就是在http://i.cnblogs.com/EditPosts.aspx?opt=1linux中实现.所以最近就将自己的代码全部迁移到linux ...

  4. 不一样的味道--Html和Xml解析、格式、遍历

    很多其它内容查看官网:http://www.tinygroup.org TinyXmlParser一切以简单.有用.高速为主. 演示样例1:Xml字符串解析 比方,我们要解析一段Xml字符串,简单例如 ...

  5. JavaScript随记汇总

    1.<script>标签嵌套,浏览器无法正常解析的问题: 百度知道回答 <script>FTAPI_slotid = 1007894;FTAPI_sync = true< ...

  6. 汇总前端最最常用的JS代码片段-你值得收藏

    原始出处,可拷贝:http://www.w3cfuns.com/notes/25068/1d0d350a974d879e63f1115cf80a3288.html 摘自:http://www.love ...

  7. vue&period;js中使用Axios

    Axios为vue2.0官方推荐HTTP请求工具,之前的是vue-resource 在使用的过程中总结了两种使用方式: 1.和vue-resource使用类似 引入:import axios from ...

  8. Android UI(四)云通讯录项目之云端更新进度条实现

    作者:泥沙砖瓦浆木匠网站:http://blog.csdn.net/jeffli1993个人签名:打算起手不凡写出鸿篇巨作的人,往往坚持不了完成第一章节.交流QQ群:[编程之美 365234583]h ...

  9. H5新特性之video audio

    1.标签 <video src="~~~" autoplay loop controls controlslist="nodownload nofullscreen ...

  10. 用户设置与virtual host配置

    1.进入localhost:15672yemian 然后选择Admin菜单. 2.添加用户 caojun/123456 3.效果 4.virtual hosts添加 相当于db. /cjhost,一般 ...