题意::从起点到终点的所有的最短路中,找出离终点有X个路口的城市一共有几个
开始我用最短路+DFS从起点开始搜,超时了
换了一种方法,从终点开始搜,AC
#include<stdio.h> int N;
const int MAX=1e9;
int use[];
int dis[];
int map[][];
bool hash[];
int tempget[];
int maxDis;
int allPoint; int start,end,shortNum; void dijk()
{
int i,j,min,rj,from;
dis[start]=;
for(i=;i<=N;i++){
min=MAX;
for(j=;j<=N;j++){
if(use[j]==)continue;
if(min>dis[j]){
min=dis[j];
rj=j;
}
}
from=rj;
for(j=;j<=N;j++){
if(use[j]==)continue;
if(dis[j]>map[from][j]+dis[from])
dis[j]=map[from][j]+dis[from];
}
use[rj]=;
}
} void dfs(int from,int leftStep,int lenth) //搜的时候从师兄所在的点开始搜
{
int i;
if(leftStep==)return ; for(i=;i<=N;i++){
if(hash[i]==)continue;
if((dis[i]+map[from][i]+lenth)!=dis[end])continue; //这样保证了从终点搜出的点都在最短路上
if(tempget[i]==){
allPoint++;tempget[i]=;
}
hash[i]=;
dfs(i,leftStep-,lenth+map[from][i]);
hash[i]=;
}
} int main()
{
int m,i,j,k;
while(scanf("%d%d",&N,&m)!=EOF){
int ll,rr,v; start=N;
end=;
allPoint=;
scanf("%d",&maxDis); for(i=;i<=N;i++){
for(j=;j<=N;j++){
map[i][j]=MAX;
hash[i]=;
}
dis[i]=MAX;
use[i]=;
tempget[i]=;
} for(i=;i<=m;i++){
scanf("%d%d%d",&ll,&rr,&v);
if(map[ll][rr]>v){
map[ll][rr]=map[rr][ll]=v;
}
} dijk();
tempget[]=end;
allPoint++;
dfs(end,maxDis,); printf("%d\n",allPoint);
} return ;
}
题目1539:师弟 ——最短路+DFS的更多相关文章
-
PAT-1111 Online Map (30分) 最短路+dfs
明天就要考PAT,为了应付期末已经好久没有刷题了啊啊啊啊,今天开了一道最短路,状态不是很好 1.没有读清题目要求,或者说没有读完题目,明天一定要注意 2.vis初始化的时候从1初始化到n,应该从0开始 ...
-
HDU_1142(最短路 + dfs)
Jimmy experiences a lot of stress at work these days, especially since his accident made working dif ...
-
HDU 1142 A Walk Through the Forest(最短路+dfs搜索)
A Walk Through the Forest Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Jav ...
-
cf1051F. The Shortest Statement(最短路/dfs树)
You are given a weighed undirected connected graph, consisting of nn vertices and mm edges. You shou ...
-
Let‘s play computer game(最短路 + dfs找出所有确定长度的最短路)
Let's play computer game Description xxxxxxxxx在疫情期间迷上了一款游戏,这个游戏一共有nnn个地点(编号为1--n1--n1--n),他每次从一个地点移动 ...
-
借助leetcode题目来了解BFS和DFS
广度优先和深度优先搜索 前言 看着这两个搜索的前提的是读者具备图这一数据结构的基本知识,这些可以直接百度一波就了解了.图也像树一样,遍历具有很多的学问在里面,下面我将借用leetcode的题目讲解一下 ...
-
449. Serialize and Deserialize BST——几乎所有树的面试题目都会回到BFS或者DFS,使用BFS,None节点存#
Serialization is the process of converting a data structure or object into a sequence of bits so tha ...
-
题目1447:最短路(Floyd算法)
题目链接:http://ac.jobdu.com/problem.php?pid=1447 详解链接:https://github.com/zpfbuaa/JobduInCPlusPlus 参考代码: ...
-
九度oj 题目1447:最短路
题目描述: 在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt.但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线 ...
随机推荐
-
如何启动免安装版Tomcat并将Tomcat添加到服务中
1.安装jdk,并配置环境变量 (1)在Path中添加 F:\Program Files\Java\jdk1.8.0_25\bin (2)添加一个JAVA_HOME变量,变量值为F:\Program ...
-
查看远程git log
$ git reset --hard bit/add $ git log --oneline --graph
-
HDU 3374 String Problem(KMP+最大/最小表示)
String Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) T ...
-
drop、 truncate 、 delete
相同点: truncate和不带where子句的delete, 以及drop都会删除表内的数据 不同点: 1. truncate和 delete只删除数据不删除表的结构 drop语句将删除表的 ...
-
Kooboo CMS的安装步骤
Kooboo CMS的安装步骤 来自Kooboo document 跳转到: 导航, 搜索 http://www.microsoft.com/web/gallery/install.aspx?appi ...
-
Dialog 顶部黑线问题
Dialog 顶部黑线问题 样式如下: [java] view plaincopyprint? <style name="Transparent_Dialog"> &l ...
-
MVC中Filter拦截问题记录之重定向陷阱
出错环境:被拦截的页面中使用了未实例化的对象,比如只有登录后才有的UserInfor对象. 理想中:浏览器请求页面时,会被Filter拦截,然后重定向到指定页面: 实际现象:将断点打入Filter中, ...
-
JSONP跨域的原理解析[转]
转自 http://www.nowamagic.net/librarys/veda/detail/224 JavaScript是一种在Web开发中经常使用的前端动态脚本技术.在JavaScript中, ...
-
SDL OPENGL 在linux ubuntu示例
gl画纹理texture /* * SDL OpenGL Tutorial. * (c) Michael Vance, 2000 * briareos@lokigames.com * * Distri ...
-
9、RabbitMQ-集成Spring
spring封装RabbitMQ看官网:https://spring.io/projects/spring-amqp#learn 开发时根据官网的介绍进行开发,具体的说明都有具体的声明 1.导入依赖 ...