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)


相关推荐

  • C语言实现五子棋小游戏

    C语言实现五子棋小游戏三子棋,五子棋,无论多少子棋,其原理都是一样的。下面我用五子棋为例讲解用C语言多文件编程实现五子棋。设计电脑和玩家两个作为下棋的两方,用键盘输入作为玩家的游戏操作。1.效果图:程序总的构架:我们只要输入坐标就可以和电脑对弈了。电脑的棋子用‘0’表示,玩家的棋子用‘x’表示。2.打印菜单可以根据自己的爱好设计各种风格的…

  • python 脚本实现查看文件内容

    python 脚本实现查看文件内容

  • 数字信号处理–语音信号处理

    数字信号处理–语音信号处理在Matlab平台上语音信号处理

  • 圆圈正义读后感_为了公平正义观后感800

    圆圈正义读后感_为了公平正义观后感800圆圈正义半书观后感​ 这段时间读了一本书,名字叫《圆圈正义》,这本书的作者是罗翔,可能大家在抖音上经常刷到过,人称法外狂徒张三,经常会用很有趣的语言来讲述法律知识。​ 我认识他是因为他说过一段话:“我们登上我们并非我们所选择的舞台,演出并非我们所选择的剧本,我们这一生中自己能够决定的东西很少,我们可能能决定5%的东西,但95%的东西是我们决定不了的,我们决定不了我们的出生,我们决定不了我们的智商,我们更决定不了我们这一生的贵人相助,很多时候我们经常会羡慕别人,但是没有谁的剧本值得羡慕,你只能把你自己

    2022年10月22日
  • YAML/Properties配置文件与Spring Boot(转)

    YAML/Properties配置文件与Spring Boot(转)

  • MATLAB优化函数fmincon解析[通俗易懂]

    MATLAB优化函数fmincon解析[通俗易懂]MATLAB,优化函数fmincon解析[x,fval,exitflag,output,lambda,grad,hessian]=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options);…

发表回复

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

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