hdu1142_hdu1001

hdu1142_hdu1001这道题纠结了好久~~~最后发现最短路的算法求错了~~~可是以前用此代码AC了好几道题了~~~汗~~求指点~先是最后ac代码:#include#include#include#include#defineINF1000010010usingnamespacestd;intd[1005];intvis[1005];intw[1005][1005];

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

Jetbrains全系列IDE稳定放心使用

这道题纠结了好久~~~最后发现最短路的算法求错了~~~

可是以前用此代码AC了好几道题了~~~汗~~求指点~

先是最后ac代码:

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define INF 1000010010
using namespace std;
int d[1005];
int vis[1005];
int w[1005][1005];
int s[1005];
void init(int n)
{
    memset(s,0,sizeof(s));
    memset(vis,0,sizeof(vis));
    int i,j;
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=n;j++)
        {
            w[i][j]=INF;
            if(i==j)
                w[i][j]=0;
        }
        d[i]=INF;
    }
}
int DFS(int k,int n)
{
    if(s[k])
        return s[k];
     if(k == 2)
        return 1;
    for(int i=1; i<=n; i++)
     {
         if(w[k][i]!=INF && d[k]>d[i])
            s[k]+=DFS(i,n);
   }
    return s[k];
}
struct cmp
{
    bool operator()(int a,int b)
    {
        return a>b;
    }
};
int main()
{
    int n,m;
    while(scanf("%d",&n),n!=0)
    {
        init(n);
        scanf("%d",&m);
        int i,a,b,d1;
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&d1);
            if(d1<w[a][b])
                w[a][b]=w[b][a]=d1;
        }

        d[2]=0;
        //priority_queue<int,vector<int>,cmp> q;
        typedef pair<int,int> pii;
        priority_queue<pii,vector<pii>,greater<pii> > q;
        q.push(make_pair(d[2],2));
        while(!q.empty())
        {
            pii t1=q.top();
            q.pop();
            int t=t1.second;
            if(vis[t])
                continue;
            vis[t]=1;
            for(i=1;i<=n;i++)
            {
                if(!vis[i]&&d[i]>d[t]+w[t][i])
                {
                    d[i]=d[t]+w[t][i];
                    q.push(make_pair(d[i],i));
                }
            }
        }

        printf("%d\n",DFS(1,n));

    }
    return 0;
}

然后是WA的代码:

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define INF 1000010010
using namespace std;
int d[1005];
int vis[1005];
int w[1005][1005];
int s[1005];
void init(int n)
{
    memset(s,0,sizeof(s));
    memset(vis,0,sizeof(vis));
    int i,j;
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=n;j++)
        {
            w[i][j]=INF;
            if(i==j)
                w[i][j]=0;
        }
        d[i]=INF;
    }
}
int DFS(int k,int n)
{
    if(s[k])
        return s[k];
     if(k == 2)
        return 1;
    for(int i=1; i<=n; i++)
     {
         if(w[k][i]!=INF && d[k]>d[i])
            s[k]+=DFS(i,n);
   }
    return s[k];
}
struct cmp
{
    bool operator()(int a,int b)
    {
        return d[a]>d[b];             //此处修改
    }
};
int main()
{
    int n,m;
    while(scanf("%d",&n),n!=0)
    {
        init(n);
        scanf("%d",&m);
        int i,a,b,d1;
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&d1);
            if(d1<w[a][b])
                w[a][b]=w[b][a]=d1;
        }

        d[2]=0;
        priority_queue<int,vector<int>,cmp> q;         //此处修改
        //typedef pair<int,int> pii;
        //priority_queue<pii,vector<pii>,greater<pii> > q;
        q.push(2);
        while(!q.empty())
        {
            int t=q.top();
            q.pop();
            //int t=t1.second;
            if(vis[t])
                continue;
            vis[t]=1;
            for(i=1;i<=n;i++)
            {
                if(!vis[i]&&d[i]>d[t]+w[t][i])
                {
                    d[i]=d[t]+w[t][i];
                    q.push(i);              //此次修改~~
                }
            }
        }

        printf("%d\n",DFS(1,n));

    }
    return 0;
}

感觉对的~~但是wa了 难道priority queue 用法有误么~~

~~知道问题了~~原来是priority_queue有问题~看看实现就知道了~q.push().q.pop() 都会排序

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

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

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

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

(0)


相关推荐

  • pycharm写脚本_pycharm运行python脚本

    pycharm写脚本_pycharm运行python脚本打开pycharm,file->setting在右侧模板框图中填写模板##!/usr/bin/python3#-*-coding:utf-8-*-#@Time:${DATE}${TIME}#@Author:${USER}#@Email:wayne_lau@aliyun.com#@File:${NAME}.py#@Project:${PROJECT_NAME}其他可用的预定义文件模板变量为:${PROJECT_NAME}-.

  • webstorm插件推荐_webstorm中文界面

    webstorm插件推荐_webstorm中文界面1.activate-power-mode狂拽炫酷吊炸天装逼的插件,atom上的神器啊,抱着试一试的心态一搜,webstorm上居然也有了,安装之后可以在window->activate-power-mode中关闭震动以及开启彩色模式。2.TabNine可以记录用户习惯自动补全代码,牛逼3.ESLint代码检查插件4.RainbowBrackets彩虹色的括号,颜色可以自行调整,代码块看起来更清晰在这里插入图片描述5.CodeG.

  • vi 命令 使用方法

    vi 命令 使用方法

    2021年11月14日
  • CAS原理详解_外燃机工作原理

    CAS原理详解_外燃机工作原理CAS简介CAS的意思是compareandswap,比较并交换。CAS的引入是为了解决java锁机制带来的性能问题。锁机制存在以下问题:(1)在多线程竞争下,加锁、释放锁会导致比较多的上下文切换和调度延时,引起性能问题。(2)一个线程持有锁会导致其它所有需要此锁的线程挂起。(3)如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置,引起性能风险。解决线程安全问题volatile是不错的机制,但是volatile不能保证原子性。因此对于同步最终还是要回到锁机制上来。独占锁

    2022年10月16日
  • linux系统移植的一般过程_内核移植的基本步骤

    linux系统移植的一般过程_内核移植的基本步骤在众多嵌入式操作系统中,Linux目前发展最快、应用最为广泛。性能优良、源码开放的Linux具有体积小、内核可裁减、网络功能完善、可移植性强等诸多优点,非常适合作为嵌入式操作系统。一个最基本的Linux操作系统应该包括:引导程序、内核与根文件系统三部分。  嵌入式Linux系统移植主要由四大部分组成:  一、搭建交叉开发环境  二、bootloader的选择和移植  三、kernel的配置、编译、…

发表回复

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

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