D. Made In Heaven_海边拾贝的言的博客-程序员宅基地

技术标签: 图论  搜索  

K短路A*算法



#include<bits/stdc++.h>
using namespace std;
#define INF 0xffffff
const int MAXN = 2e6;
typedef long long ll;
struct node
{
    ll to;
    ll val;
    ll next;
};
struct node2
{
    ll to;
    ll g,f;
    bool operator<(const node2 &r ) const  
    {  
        if(r.f==f)  
            return r.g<g;  
        return r.f<f;  
    }   
};
node edge[MAXN],edge2[MAXN];
ll n,m,s,t,k,cnt,cnt2,ans;
ll dis[1010],visit[1010],head[1010],head2[1010];
void init()
{
    memset(head,-1,sizeof(head));
    memset(head2,-1,sizeof(head2));
    cnt=cnt2=1;
}
void addedge(ll from,ll to,ll val)
{
    edge[cnt].to=to;
    edge[cnt].val=val;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}
void addedge2(ll from,ll to,ll val)
{
    edge2[cnt2].to=to;
    edge2[cnt2].val=val;
    edge2[cnt2].next=head2[from];
    head2[from]=cnt2++;
}
bool spfa(ll s,ll n,ll head[],node edge[],ll dist[])  
{  
    queue<int>Q1;  
    ll inq[1010];  
    for(ll i=0;i<=n;i++)  
    {  
        dis[i]=INF;  
        inq[i]=0;  
    }  
    dis[s]=0;  
    Q1.push(s);  
    inq[s]++;  
    while(!Q1.empty())  
    {  
        ll q=Q1.front();  
        Q1.pop();  
        inq[q]--;  
        if(inq[q]>n)
            return false;  
        ll k=head[q];  
        while(k>=0)  
        {  
            if(dist[edge[k].to]>dist[q]+edge[k].val)  
            {  
                dist[edge[k].to]=edge[k].val+dist[q];  
                if(!inq[edge[k].to])  
                {  
                    inq[edge[k].to]++;  
                    Q1.push(edge[k].to);  
                }  
            }  
            k=edge[k].next;  
        }  
    }  
    return true;  
}
ll A_star(ll s,ll t,ll n,ll k,ll head[],node edge[],ll dist[]) 
{  
    node2 e,ne;  
    ll cnt=0;  
    priority_queue<node2>Q;  
    if(s==t)
        k++;  
    if(dis[s]==INF)  
        return -1;  
    e.to=s;  
    e.g=0;  
    e.f=e.g+dis[e.to];  
    Q.push(e);  

    while(!Q.empty())  
    {  
        e=Q.top();  
        Q.pop();  
        if(e.to==t)//找到一条最短路径  
        {  
            cnt++;  
        }  
        if(cnt==k)//找到k短路  
        {  
            return e.g;  
        }  
        for(ll i=head[e.to]; i!=-1; i=edge[i].next)  
        {  
            ne.to=edge[i].to;  
            ne.g=e.g+edge[i].val;  
            ne.f=ne.g+dis[ne.to];  
            Q.push(ne);  
        }  
    }  
    return -1;  
}  
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        scanf("%lld%lld%lld",&s,&t,&k);
        ll tt;
        cin>>tt;
        for(ll i=1;i<=m;i++)
        {
            ll a,b,c;
            scanf("%lld%lld%lld",&a,&b,&c);
            addedge(a,b,c);
            addedge2(b,a,c);
        }
        spfa(t,n,head2,edge2,dis);
        ans=A_star(s,t,n,k,head,edge,dis);
        if(ans>tt || ans == -1) puts("Whitesnake!");     
        else puts("yareyaredawa");   
     }

    return 0;
} 
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_38686780/article/details/82533985

智能推荐

上交大 2011 二次方程计算器_dixiang1123的博客-程序员宅基地

题目:输入关于x的二次方程表达式(系数为整数),输出两个解(由小到大输出,保留两位小数);如果无解,则输出“No Solution”。思路:先确定等号位置,分成左右两个字符串,从中分别提取系数,再综合。然后求解。提取系数的过程如图:过程:介绍两个函数:atoi()函数可以识别"+""-"号,并正确转化成int。string str="-2980";string s...

只重写equals()但不重写hashCode会有什么后果?_1024276449的博客-程序员宅基地_不重写hashcode有什么影响

只重写equals()但不重写hashCode会有什么后果?1.如果判断两个数如果hashCode相同则equals不一定相同,反而equals相同则hashCode则一定相同。2.那么我们只重写equals()但不重写hashCode会有什么后果?如果我们不将我们重写equals方法的类放到HashSet等散列表中时则不会有什么影响,但如果放到我们的散列表中时我们的散列表则会优先比较HashCode所以可能会产生错误。...

Struts2中的设计模式_7潜伏7的博客-程序员宅基地_struts2设计模式

设计模式(Design pattern)是经过程序员反复实践后形成的一套代码设计经验的总结。设计模式随着编程语言的发展,也由最初的“编程惯例”逐步发展成为被反复使用、并为绝大多数程序员所知晓的、完善的理论体系。我们使用设计模式(Design pattern)的初衷,是使代码的重用度提高、让代码能够更容易被别人理解以及保证代码的可靠性。毫无疑问,在程序中使用设计模式无论是对于程序员自身还是对于应用程

Assemble UVALive - 3971 组装电脑_Nicolas Lee的博客-程序员宅基地

Recently your team noticed that the computer you use to practice for programming contests is notgood enough anymore. Therefore, you decide to buy a new computer. To make the ideal computer ...

ubuntu 16.06 编译 vlc for android_qq_15361657的博客-程序员宅基地

1、https://www.ubuntu.com/download      下载 ubuntu16.042、vmware workstation配置虚拟机3、下载android studio,下载sdk ndk4、配置sdk,ndk5、配置bash.profile6、git7、sh compile.sh

如何发布ArcGIS Server离线地图(google 瓦片)_weixin_44922969的博客-程序员宅基地

说明本案例实现内容:GoogleEarth瓦片地图的获取、在ArcGIS Server Manger中发布下载好的影像瓦片数据。工具准备1、BIGEMAP地图下载器http://www.bigemap.com/reader/download/2、ARCGIS10.2 http://pan.baidu.com/s/1i5uMzU93、ARCGIS SERVE...

随便推点

cf 1154G Minimum Possible LCM_二分抄代码的博客-程序员宅基地

...这题关键在他的a[i]&lt;=1e7那么我们知道lcm(a,b)=a*b/gcd(a,b);那么我们只要枚举每一个因数d,不管他是不是gcd然后找出能被这个d整除的最小的两个数字a,b那么对于这个因数d,tmp=a*b/d,ans=min(ans,tmp)由于我们枚举了1-1e7所有的质因子,所以就算a*b/d不是lcm,但之后总会枚举到a*b/gcd(a,b)而使...

java excel 加密_Java 加密/解密Excel_丸子里里的博客-程序员宅基地

概述设置excel文件保护时,通常可选择对整个工作簿进行加密保护,打开文件时需要输入密码;或者对指定工作表进行加密,即设置表格内容只读,无法对工作表进行编辑。另外,也可以对工作表特定区域设置保护,即设置指定区域可编辑或者隐藏数据公式,保护数据信息来源。无需设置文档保护时,可撤销密码保护,即解密文档。下面,将通过java程序演示以上加密、解密方法的实现。示例大纲1. Excel工作簿1.1 加密工作...

Spring Cloud 核心组件 Dubbo-Nacos_m0_37567301的博客-程序员宅基地

Spring Cloud 核心组件 Dubbo-Nacos作者:DecaMinCow博客:http://blog.csdn.net/m0_37567301邮箱:decamincow#gmail.com (#-&gt;@)Dubbo 介绍阿里研发的 RPC 框架注册中心为 nacos 的 dubbo 示例1. Provider依赖文件&lt;dependency&gt; &lt;groupId&gt;com.alibaba.cloud&lt;/groupId&gt; &l

android接收list对象数组,Android - ToDoList(定制ArrayAdapter)_席佳益的博客-程序员宅基地

ToDoList(定制ArrayAdapter)本文地址:http://blog.csdn.net/caroline_wendy/article/details/21401907前置项目参见:http://blog.csdn.net/caroline_wendy/article/details/21330733环境: Android Studio 0.5.1ArrayAdapter使用泛型(模...

STS on Eclipse 3.6_咔啡的博客-程序员宅基地

EngineeringChristian DupuisJuly 01, 2010Last week the Eclipse Foundation released the much anticipated next version of Eclipse. You can download Eclipse 3.6 aka Helios from SpringSource’s member distribution page. Also check out the New &amp; Noteworthy

js读取服务器html文件,【未解决】js中将html内容保存到服务器上的本地的html文件..._Arsd的博客-程序员宅基地

【背景】之前已经实现了:网页中,点击某个按钮,可以调用到js获得到KindEditor的html的内容:function submitGoodsContent(){var kindeditor = window.editor;// 取得HTML内容html = kindeditor.html();console.log(html);}商品名:在此输入新产品的介绍内容提交当前页面现在希望实现,不仅仅...

推荐文章

热门文章

相关标签