2013成都邀请赛J称号||HDU4725 The Shortest Path in Nya Graph(spfa+slf最短的优化)

2013成都邀请赛J称号||HDU4725 The Shortest Path in Nya Graph(spfa+slf最短的优化)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

职务地址:HDU 4725

这题卡了好长时间了,建图倒是会建,可是不会最短路的算法优化,本以为都须要堆去优化的,打算学了堆之后再来优化。可是昨晚CF的一道题。。(那题也是不优化过不了。。)然后我就知道了还有不须要堆也能够的优化。并且优化的操作非常easy,把单向队列变成双端队列即可了。详细优化思路是若d[v]比队列前端的元素的距离小,就增加队列前端,否则增加队列尾端。

非常easy吧。

。。会了后。把这题一加上slf优化就过了。

。。

事实上这题的重点在于建图。。不在于优化。。。。sad。。

这题的建图就是把层次也都抽象成两个点。一个用来出,一个用来进。我是看的kuangbin大神的博客才知道的。

详情见kuangbin大神博客。。kuangbin大神博客

懒得去的能够看以下博文文字的复制。。

N个点,然后有N层。要假如2*N个点。

总共是3*N个点。

点1~N就是相应的实际的点1~N. 要求的就是1到N的最短路。

然后点N+1 ~ 3*N 是N层拆出出来的点。

第i层,入边到N+2*i-1, 出边从N+2*i 出来。

(1<= i <= N)

N + 2*i 到 N + 2*(i+1)-1 加边长度为C. 表示从第i层到第j层。

N + 2*(i+1) 到 N + 2*i – 1 加边长度为C,表示第i+1层到第j层。

假设点i属于第u层,那么加边 i -> N + 2*u -1 N + 2*u ->i 长度都为0

然后我的代码例如以下:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;
const int INF=0x3f3f3f3f;
int vis[310000], d[310000], cnt, head[310000], n, num;
struct node
{
    int u, v, w, next;
} edge[700000];
void add(int u, int v, int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void spfa()
{
    int f1=0, f2=0, i;
    deque<int>q;
    q.push_back(1);
    memset(d,INF,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[1]=0;
    vis[1]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        vis[u]=0;
        for(i=head[u]; i!=-1; i=edge[i].next)
        {
            int v=edge[i].v;
            if(d[v]>d[u]+edge[i].w)
            {
                d[v]=d[u]+edge[i].w;
                if(!vis[v])
                {
                    vis[v]=1;
                    if(!q.empty()&&d[v]<d[q.front()])
                    {
                        q.push_front(v);
                    }
                    else
                        q.push_back(v);
                }
            }
        }
    }
    if(d[n]==INF)
        d[n]=-1;
    printf("Case #%d: %d\n",num,d[n]);
}
int main()
{
    int t, u, v, w, m, c, i;
    num=0;
    scanf("%d",&t);
    while(t--)
    {
        num++;
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        cnt=0;
        scanf("%d%d%d",&n,&m,&c);
        for(i=1; i<=n; i++) //将第i个边与该边所属的层次u相连。
        {
            scanf("%d",&u);
            add(i,n+2*u-1,0);
            add(n+2*u,i,0);
        }
        for(i=1; i<n; i++) //将每两个相邻的层次互连
        {
            add(n+2*i+1,n+2*i,c);
            add(n+2*i-1,n+2*i+2,c);
        }
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        spfa();
    }
    return 0;
}

版权声明:本文博客原创文章。博客,未经同意,不得转载。

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

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

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

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

(0)


相关推荐

  • 命令行升级pip_pip升级版本命令

    命令行升级pip_pip升级版本命令查询当前pythonpip版本:pipshowpip输入python-mpipinstall–upgradepip命令升级;报错:ERROR:CouldnotinstallpackagesduetoanEnvironmentError:[WinError5]拒绝访问。:‘c:\programfiles\python37\lib\site-packages\pip-19.2.3.dist-info\entry_points.txt’Considerusin.

    2022年10月31日
  • C#中splitContainer用法

    C#中splitContainer用法在这个例子中,最上方是一个menustrip控件,其下市toolstrip控件,添加为快捷按钮。中间区域是一个splitcontainer,分为panel1和panel2.(1)IsMdiContainer–>true(2)splitContainer的具体用法:a)他不能直接用鼠标点击选中,只能右击-》选中splitContainerb)此时我们的窗体不

  • 利用flex实现元素水平垂直居中[通俗易懂]

    利用flex实现元素水平垂直居中[通俗易懂]首先介绍一下flex布局。采用Flex布局的元素,称为Flex容器(flexcontainer),简称“容器”。它的所有子元素自动成为容器成员,成为flex项目(flexitem),简称“项目”。容器默认存在两根轴:水平的主轴(mainaxis)和垂直的交叉轴(crossaxis)。主轴的开始位置(与边框的交叉点)叫做mainstart,结束位置叫做mainend;交叉轴的开始…

  • openCV基本绘图函数—-画圆函数cvCircle

    openCV基本绘图函数—-画圆函数cvCircle#include #include#include usingnamespacecv; intmain(intargc,char**argv){    IplImage*img=cvLoadImage(“D:\\123\\2.jpg”,1);    cvCircle(img,cvPoint(120,120),90,c

  • 联想笔记本电脑键盘亮了屏幕不亮_联想笔记本电脑键盘为什么不亮

    联想笔记本电脑键盘亮了屏幕不亮_联想笔记本电脑键盘为什么不亮现在不管是工作还是学习,已经离不开电脑了,它的出现带给我们极大的方便,笔记本以它小巧灵活的体积更是受到了很多学生和商务人士的喜欢,可是市面上有那么多品牌的笔记本,应该怎么正确做出选择呢?下面小编就为大家带来联想笔记本电脑开机键亮但是黑屏,联想笔记本键盘没反应?联想笔记本电脑开机键亮但是黑屏1、若遇到联想笔记本电脑开机键亮但是黑屏的情况,可以拆卸掉笔记本背面的电池,只用电源适配器连接电脑,尝试开机一…

  • 堆栈callstack打印

    堆栈callstack打印一、适用java1、Log.d(TAG,Log.getStackTraceString(newThrowable()));//在使用Log.d的场合2、newException(“testprintkstack”).printStackTrace();Note:还有其他方法,可以参考网络

    2022年10月25日

发表回复

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

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