有n个城市，m条道路，每个城市都有加油站，加油的花费都不一样，在道路上行驶的耗油即为道路权值，给q次询问，问油箱容量为C的车从s到t的最小花费是多少

• 用当前的城市加剩余的油量表示一个状态，利用优先队列（把花费小的放在队首）即可
• 注意：城市从0开始编号，优先队列要注意初始化（或直接定义在bfs里）

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 using namespace std; 8 9 #define inf (1 << 28)10 #define res register int11 inline int read()12 {13 int x(0),f(1); char ch;14 while(!isdigit(ch=getchar())) if(ch=='-') f=-1;15 while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();16 return f*x;17 }18 19 struct node{20 int city,rest,cost;21 bool operator <(const node &n2) const{22 return cost>n2.cost;}23 };24 25 const int N=1010,M=10010; 26 int n,m;27 int head[N],val[N],ver[M<<1],nxt[M<<1],edge[M<<1],tot;28 int d[N][200];//city fuel_rest29 int vis[N][200];30 //汽车在城市x，剩余油量位fuel_rest时的最小花费 31 inline void add(int x,int y,int z) 32 {ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot; edge[tot]=z;}33 34 priority_queue
            
              q;35 inline void bfs(int s,int t,int C)36 {37 while(q.size()) q.pop();38 memset(vis,0,sizeof(vis));39 for(res i=1 ; i<=n ; i++)40 for(res j=0 ; j<=C ; j++)41 d[i][j]=inf;42 q.push((node){s,0,0}); 43 d[s][0]=0;44 while(q.size())45 {46 node now=q.top(); q.pop();47 int x=now.city,re=now.rest,cos=now.cost;48 if(x==t) { return;}//cout<<"fuck "<
             
              <
              
               =z && d[y][re-z]>d[x][re])61 {62 d[y][re-z]=d[x][re];63 q.push((node){y,re-z,d[y][re-z]});64 }65 }66 }67 return ;68 }69 70 int main()71 {72 n=read(); m=read();73 for(res i=1 ; i<=n ; i++) val[i]=read();74 for(res i=1 ; i<=m ; i++)75 {76 int x=read()+1,y=read()+1,z=read(); 77 add(x,y,z); add(y,x,z);78 }79 80 int q=read();81 for(res i=1 ; i<=q ; i++)82 {83 int cap=read(),s=read()+1,t=read()+1;84 bfs(s,t,cap);85 int ans=d[t][0];86 if(ans>=inf) puts("impossible");87 else printf("%d\n",ans);88 }89 return 0;90 }