扩展代价是任意数值,等价于一般的最短路问题,使用优先队列,复杂度$N$$logN$
#include<bits/stdc++.h>
using namespace std;
const int N=1010,C=110,M=2e4+10,INF=0x3f3f3f3f; //无向图M开两倍
int h[N],e[M],w[M],ne[M],idx;
int dist[N][C]; //将花费看做dist
bool st[N][C];
int price[N];
int n,m;
struct Ver{
int d,u,c;
bool operator< (const Ver &W) const{
return d>W.d;
}
};
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dijkstra(int cap,int start,int end){
memset(dist,INF,sizeof(dist));
memset(st,false,sizeof st);
dist[start][0]=0;
priority_queue<Ver> heap;
heap.push({0,start,0});
while(!heap.empty()){
Ver t=heap.top();
heap.pop();
if(t.u == end&&t.c==0) return dist[end][0]; //t.c==0可以不加,根据有限队列,第一次遍历肯定是花费最小的,一定为0
if(st[t.u][t.c]) continue;
st[t.u][t.c]=true;
if(t.c+1<=cap){
if(t.d+price[t.u]<dist[t.u][t.c+1]){
dist[t.u][t.c+1]=t.d+price[t.u];
heap.push({dist[t.u][t.c+1],t.u,t.c+1});
}
}
for(int i=h[t.u];i!=-1;i=ne[i]){
int j=e[i];
if(t.c>=w[i]){
if(t.d<dist[j][t.c-w[i]]){
dist[j][t.c-w[i]]=t.d;
heap.push({dist[j][t.c-w[i]],j,t.c-w[i]});
}
}
}
}
return -1;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>price[i];
memset(h,-1,sizeof(h));
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
int q;
cin>>q;
for(int i=0;i<q;i++){
int c,s,e;
cin>>c>>s>>e;
int res=dijkstra(c,s,e);
if(res==-1) cout<<"impossible"<<endl;
else cout<<res<<endl;
}
}
复杂度不对吧,每个点最多可以被枚举C次,复杂度应该是$c(n + m)log(cn)$吧
%%%