UVA11367 Full Tank?

洛咕

题意:\(N(N<=1000)\)个城市\(M(M<=10000)\)条无向边.每个城市里有一个加油站,加城市\(i\)一升油花费\(cost[i]\)元,通过一条道路的油耗就是该边的边权.回答不超过100次询问:油箱容量为\(C(C<=100)\)的车子,从起点S到终点T的最小花费?

分析:每个状态我们需要记录三个信息:城市编号为id,剩余油量为now,最小花费为val.我们把这些状态放入一个(按照val从小到大排序的)优先队列.

每次取出堆顶,有两种方式拓展:

1,加油.若\(now<C\),可以扩展到\((id,now+1,val+cost[id])\)

2,跑路.若\(w[id][v]<=now\),可以扩展到\((v,now-w[id][v],val)\)

当我们第一次从堆顶取出终点时,就是最小花费.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1005;
const int M=20005;
int n,m,C,s,t;
int cost[N],visit[N][105];
int tot,head[N],nxt[M],to[M],w[M];
inline void add(int a,int b,int c){
    nxt[++tot]=head[a];head[a]=tot;
    to[tot]=b;w[tot]=c;
}
struct node{
    int id,now,val;
    bool operator <(const node &x)const{
        return val>x.val;
    }
}temp,tmp;
inline void bfs(){
    priority_queue<node>q;while(q.size())q.pop();//初始化优先队列
    temp.id=s;temp.now=0;temp.val=0;q.push(temp);
    for(int i=0;i<n;++i)
        for(int j=0;j<=C;++j)
            visit[i][j]=0;
    while(q.size()){
        temp=q.top();q.pop();
        int u=temp.id,res=temp.now,cnt=temp.val;
        if(u==t){
            printf("%d\n",cnt);
            return;
        }
        visit[u][res]=1;
        if(res<C&&!visit[u][res+1]){//拓展1
            tmp.id=u;
            tmp.now=res+1;
            tmp.val=cnt+cost[u];
            q.push(tmp);
        }
        for(int i=head[u];i!=-1;i=nxt[i]){//拓展2
            int v=to[i];
            if(w[i]<=temp.now&&!visit[v][res-w[i]]){
                tmp.id=v;
                tmp.now=res-w[i];
                tmp.val=cnt;
                q.push(tmp);
            }
        }
    }
    puts("impossible");
}
int main(){
    n=read();m=read();
    for(int i=0;i<n;++i)cost[i]=read(),head[i]=-1;
//因为有编号为0的节点,所以head初值赋为-1;
    for(int i=1;i<=m;++i){
        int a=read(),b=read(),c=read();
        add(a,b,c);add(b,a,c);
    }
    int T=read();
    while(T--){
        C=read(),s=read(),t=read();
        bfs();
    }
    return 0;
}

UVA11367 Full Tank?

原文：https://www.cnblogs.com/PPXppx/p/11406876.html