首页 / 算法 / 《算法竞赛进阶指南》0x26广搜变形 POJ3635

《算法竞赛进阶指南》0x26广搜变形 POJ3635

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《算法竞赛进阶指南》0x26广搜变形 POJ3635，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1782字，纯文字阅读大概需要3分钟。

内容图文

题目链接：http://poj.org/problem?id=3635

题目和最短路算法的形式很像，只要对每个状态确定转移的分支即可，其中每次油量只加一，因为后续一定会在队列中被取出来重新加一（如果可以的话）

代码： 

#include<iostream>
#include<cstring>
#include<queue>
usingnamespace std;
#define maxn 1005
int head[maxn],nxt[maxn*20+10],ver[maxn*20+10],len[maxn*20+10];
int d[maxn][105];
int n,m,q;
bool vis[maxn][105];
int price[maxn];
int tot=0;
struct node{
    int dist,city,fuel;
    booloperator < (const node &a)const{
        return dist>a.dist;
    }
    node(){}
    node(int d,int c,int f):dist(d),city(c),fuel(f){}
};
void addedge(int u,int v,int w){
    ver[++tot]=v;
    len[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
}
int bfs(int start ,int end,int cab){
    priority_queue<node> q;
    memset(d,0x3f,sizeof(d));
    memset(vis,false,sizeof(vis));
    q.push(node(0,start,0));
    
    while(!q.empty()){
        node cur=q.top();
        q.pop();
        if(cur.city == end)return cur.dist;//第一次出队一定是到达终点的最小花费 int city=cur.city,fuel=cur.fuel,dist=cur.dist;
        
        if(vis[city][fuel])continue;
        vis[city][fuel]=1;
        if(fuel+1<=cab && d[city][fuel+1]>dist+price[city]){
            d[city][fuel+1]=dist+price[city];
            q.push(node(d[city][fuel+1],city,fuel+1));
        }
        for(int i=head[city];i;i=nxt[i]){
            int to=ver[i],length=len[i];
            if(length <= fuel){
                if(d[to][fuel-length] > dist)
                {
                    d[to][fuel-length]=dist;
                    q.push(node(dist,to,fuel-length));
                }
            }
        }
    }
    return -1; 
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)scanf("%d",&price[i]);
    
    int u,v, w;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }
    
    cin>>q;
    int st,ed,ca;
    while(q--){
        scanf("%d%d%d",&ca,&st,&ed);
        int ans=bfs(st,ed,ca);
        if(ans==-1)cout<<"impossible"<<endl;
        else cout<<ans<<endl;
    }
    return0;
}

 

原文：https://www.cnblogs.com/randy-lo/p/13170011.html

内容总结

以上是互联网集市为您收集整理的《算法竞赛进阶指南》0x26广搜变形 POJ3635全部内容，希望文章能够帮你解决《算法竞赛进阶指南》0x26广搜变形 POJ3635所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

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

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1143222.html

来源：【匿名】