题目1539:师弟 ——最短路+DFS

时间:2022-09-11 23:33:30

题意::从起点到终点的所有的最短路中,找出离终点有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的更多相关文章

  1. PAT-1111 Online Map &lpar;30分&rpar; 最短路&plus;dfs

    明天就要考PAT,为了应付期末已经好久没有刷题了啊啊啊啊,今天开了一道最短路,状态不是很好 1.没有读清题目要求,或者说没有读完题目,明天一定要注意 2.vis初始化的时候从1初始化到n,应该从0开始 ...

  2. HDU&lowbar;1142&lpar;最短路 &plus; dfs&rpar;

    Jimmy experiences a lot of stress at work these days, especially since his accident made working dif ...

  3. 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 ...

  4. cf1051F&period; The Shortest Statement(最短路&sol;dfs树)

    You are given a weighed undirected connected graph, consisting of nn vertices and mm edges. You shou ...

  5. Let&OpenCurlyQuote;s play computer game(最短路 &plus; dfs找出所有确定长度的最短路)

    Let's play computer game Description xxxxxxxxx在疫情期间迷上了一款游戏,这个游戏一共有nnn个地点(编号为1--n1--n1--n),他每次从一个地点移动 ...

  6. 借助leetcode题目来了解BFS和DFS

    广度优先和深度优先搜索 前言 看着这两个搜索的前提的是读者具备图这一数据结构的基本知识,这些可以直接百度一波就了解了.图也像树一样,遍历具有很多的学问在里面,下面我将借用leetcode的题目讲解一下 ...

  7. 449&period; Serialize and Deserialize BST——几乎所有树的面试题目都会回到BFS或者DFS,使用BFS,None节点存&num;

    Serialization is the process of converting a data structure or object into a sequence of bits so tha ...

  8. 题目1447:最短路&lpar;Floyd算法&rpar;

    题目链接:http://ac.jobdu.com/problem.php?pid=1447 详解链接:https://github.com/zpfbuaa/JobduInCPlusPlus 参考代码: ...

  9. 九度oj 题目1447:最短路

    题目描述: 在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt.但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线 ...

随机推荐

  1. 如何启动免安装版Tomcat并将Tomcat添加到服务中

    1.安装jdk,并配置环境变量 (1)在Path中添加 F:\Program Files\Java\jdk1.8.0_25\bin (2)添加一个JAVA_HOME变量,变量值为F:\Program ...

  2. 查看远程git log

    $ git reset --hard bit/add $ git log --oneline --graph

  3. HDU 3374 String Problem(KMP&plus;最大&sol;最小表示)

    String Problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) T ...

  4. drop、 truncate 、 delete

    相同点: truncate和不带where子句的delete, 以及drop都会删除表内的数据     不同点: 1. truncate和 delete只删除数据不删除表的结构 drop语句将删除表的 ...

  5. Kooboo CMS的安装步骤

    Kooboo CMS的安装步骤 来自Kooboo document 跳转到: 导航, 搜索 http://www.microsoft.com/web/gallery/install.aspx?appi ...

  6. Dialog 顶部黑线问题

    Dialog 顶部黑线问题 样式如下: [java] view plaincopyprint? <style name="Transparent_Dialog"> &l ...

  7. MVC中Filter拦截问题记录之重定向陷阱

    出错环境:被拦截的页面中使用了未实例化的对象,比如只有登录后才有的UserInfor对象. 理想中:浏览器请求页面时,会被Filter拦截,然后重定向到指定页面: 实际现象:将断点打入Filter中, ...

  8. JSONP跨域的原理解析&lbrack;转&rsqb;

    转自 http://www.nowamagic.net/librarys/veda/detail/224 JavaScript是一种在Web开发中经常使用的前端动态脚本技术.在JavaScript中, ...

  9. SDL OPENGL 在linux ubuntu示例

    gl画纹理texture /* * SDL OpenGL Tutorial. * (c) Michael Vance, 2000 * briareos@lokigames.com * * Distri ...

  10. 9、RabbitMQ-集成Spring

    spring封装RabbitMQ看官网:https://spring.io/projects/spring-amqp#learn 开发时根据官网的介绍进行开发,具体的说明都有具体的声明 1.导入依赖 ...