hdu 1142_hdu1001

hdu 1142_hdu1001【最短路问题】第一道最短路问题+DFS各种WARE还是在参照大神的代码的情况下 http://acm.hdu.edu.cn/showproblem.php?pid=1142只是照搬自己熟悉下过程dijkstra+dfs#include<cstdio>#include<cstring>#defineINF2000000000#defineN101…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

【最短路问题】

第一道 最短路问题+DFS 各种WA RE 还是在参照大神的代码的情况下

 

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

只是照搬 自己熟悉下过程 dijkstra+dfs

#include <cstdio>
#include <cstring>
#define INF 2000000000
#define N 1010
using namespace std;

int map[N][N],lowcost[N],visited[N],d[N],p[N];

void dijkstra(int s,int n)
{
    int i,j,k,min;
    memset(visited,0,sizeof(visited));

    for(i=1;i<=n;i++)
    {
        lowcost[i]=map[s][i];
    }
    d[s]=0;visited[s]=1;
    for(i=1;i<n;i++)
    {
        min=INF;k=i;
        for(j=1;j<=n;j++)
        {
            if(!visited[j]&&min>lowcost[j])
            {
                min=lowcost[j];
                k=j;
            }
        }
        d[k]=min;visited[k]=1;
        for(j=1;j<=n;j++)
        {
            if(!visited[j]&&lowcost[j]>d[k]+map[k][j]) //visited[j] 错误写成visited
            {                                       // d[k]+map[k][j] 会 ACCESS_VIOLATION
                lowcost[j]=d[k]+map[k][j];
            }

        }
    }

}
int DFS(int s,int n)
{
    if(p[s]) return p[s];
    if(s==2) return 1;
    int i,sum;
    sum=0;

    for(i=1;i<=n;i++)
    {
        if(map[s][i]<INF&&d[s]>d[i])
        {
            if(p[i]) sum+=p[i];
            else sum+=DFS(i,n);
        }
    }
    sum=sum+p[s];
    p[s]=sum;
    return p[s];
}
int main()
{
    int i,j,n,m,t1,t2,w;
    while(scanf("%d",&n),n)
    {
        scanf("%d",&m);
        memset(p,0,sizeof(p));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                map[i][j]=(i==j?0:INF);
            }
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&t1,&t2,&w);
            map[t1][t2]=map[t2][t1]=w;
        }
        dijkstra(2,n);
        printf("%d\n",DFS(1,n));
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/187133.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 让你彻底理解浅拷贝和深拷贝的区别是什么_怎么让文件无法拷贝

    让你彻底理解浅拷贝和深拷贝的区别是什么_怎么让文件无法拷贝在写js的时候经常会遇到复制对象,在复制对象的过程中往往会出现新对象改变原对象等等的一些问题,今天特意梳理一下,希望能帮助到遇到这些问题的开发人员。什么是浅拷贝,深拷贝以及和他们之间的区别赋值浅拷贝深拷贝在开始梳理之前先说一下值类型和引用类型:值类型(基本类型):字符串(string)、数值(number)、布尔值(boolean)、undefined、null;引用类型:对象(Object)、数组(Array)、函数(Function);1、什么是浅拷贝,深拷贝以及和他们之间的区别

  • 旋转编码器工作原理图_编码器工作原理图解

    旋转编码器工作原理图_编码器工作原理图解一、旋转编码器的原理和特点:旋转编码器是集光机电技术于一体的速度位移传感器。当旋转编码器轴带动光栅盘旋转时,经发光元件发出的光被光栅盘狭缝切割成断续光线,并被接收元件接收产生初始信号。该信号经后继电路处理后,输出脉冲或代码信号。其特点是体积小,重量轻,品种多,功能全,频响高,分辨能力高,力矩小,耗能低,性能稳定,可靠使用寿命长等特点。1、增量式编码器增量…

  • opencv中的cvCircle函数

    opencv中的cvCircle函数定义voidcvCircle(CvArr*img,CvPointcenter,intradius,CvScalarcolor,intthickness=1,intline_type=8,intshift=0);[1]参数img 图像center 圆心坐标radius 圆形的半径color 线条的颜色thic

  • OpenCV人脸识别的原理 完整版代码

    OpenCV人脸识别的原理 完整版代码http://blog.csdn.net/yanming901012/article/details/8606183本程序首先利用从摄像头检测到的人脸图片,先进行直方图均衡化 并缩放到92*112的图片大小,然后根据train.txt的采集到的人脸模版 进行匹配识别(最好是在统一光照下,采集不同角度的人脸图片各一张) 注意:影响的极大因素在于光照,模版若与采集的图像光照不一样,识别率很低。…

  • pip更新方法

    pip更新方法pip更新方法如下:方法一:pycharm中的Terminal中更新,使用如下命令:python-mpipinstall–upgradepip方法二:删除原pip文件,重新安装例如pip文件在如下文件夹中C:\Python\Python373\Lib\site-packages我们能够知道pip20.1.1所在路径,找到它,然后删掉pip-20.1.1.dist-info文件夹。设置如下图,已不见pip的踪影。提示,packagi…

  • CentOS7关闭selinux[通俗易懂]

    1、为什么要关闭selinux初学者配置linux服务器时不成功,却没有头绪,那是因为在linux操作系统中默认开启了防火墙,SELinux也处于启动状态,一般状态为enforing。致使很多服务端口默认是关闭的。所以好多服务初学者明明配置文件正确,等验证时有时连ping也ping不通。建议初学者在未学到SELlinux与iptables之前,配置服务器把这两项都关掉。2、查看selinux状…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号