C++14(g++5.4) 解法, 执行用时: 125ms, 内存消耗: 1700K, 提交时间: 2020-08-22 15:43:02

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
typedef pair<int,pii> piii;
const int N=1e3+5;

int n,m;
int p[N];
int cnt;
int w[N*20];
int to[N*20];
int nxt[N*20];
int head[N];
int dis[N][N/10];
bool vis[N][N/10];
int c,s,e;

void add(int a,int b,int c) {
    cnt++;
    w[cnt]=c;
    to[cnt]=b;
    nxt[cnt]=head[a];
    head[a]=cnt;
}
void dijkstra() {
    memset(dis,0x3f,sizeof dis);
    memset(vis,false,sizeof vis);
    dis[s][0]=0;
    priority_queue<piii,vector<piii>,greater<piii> >q;
    q.push({0,{s,0}});
    while(!q.empty()) {
        int x=q.top().second.first;
        int t=q.top().second.second;
        if(x==e) {
            cout<<dis[x][t]<<endl;
            return;
        }
        q.pop();
        if(vis[x][t]==true) continue;
        vis[x][t]=true;
        if(t<c&&dis[x][t+1]>dis[x][t]+p[x]) dis[x][t+1]=dis[x][t]+p[x],q.push({dis[x][t]+p[x],{x,t+1}});
        for(int i=head[x];i;i=nxt[i]) {
            int y=to[i];
            if(t>=w[i]&&dis[y][t-w[i]]>dis[x][t]) dis[y][t-w[i]]=dis[x][t],q.push({dis[y][t-w[i]],{y,t-w[i]}});
        }
    }
    cout<<"impossible"<<endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>p[i];
    for(int i=1;i<=m;i++) {
        int u,v,d;
        cin>>u>>v>>d;
        add(u,v,d);
        add(v,u,d);
    }
    int q;cin>>q;
    for(int i=1;i<=q;i++) {
        cin>>c>>s>>e;
        dijkstra();
    }
    return 0;
}

C++ 解法, 执行用时: 137ms, 内存消耗: 5996K, 提交时间: 2021-09-13 12:25:57

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5,M=1e4+5;
int n,m,Q,x,y,z,a[N],cnt,hd[N],to[M<<1],nxt[M<<1],val[M<<1],c,s,t,d[N][N];
bool v[N][N],flag;
struct node{
	int val,x,r;
	friend bool operator<(node x,node y){return x.val>y.val;} 
};
priority_queue<node>q;
void add(int x,int y,int z){
	to[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt,val[cnt]=z;
}
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z),x++,y++;
		add(x,y,z),add(y,x,z);
	}
	scanf("%d",&Q);
	while(Q--){
		scanf("%d%d%d",&c,&s,&t),s++,t++;
		memset(d,0x3f,sizeof(d)),memset(v,0,sizeof(v));
		d[s][0]=0,q.push((node){0,s,0}),flag=0;
		while(q.size()){
			int x=q.top().x,r=q.top().r;q.pop();
			if(x==t){flag=1,printf("%d\n",d[x][r]);break;}
			if(v[x][r]) continue;
			v[x][r]=1;
			if(r<c&&d[x][r+1]>d[x][r]+a[x]) d[x][r+1]=d[x][r]+a[x],q.push((node){d[x][r+1],x,r+1});
			for(int i=hd[x];i;i=nxt[i]){
				int y=to[i],z=val[i];
				if(z<=r&&d[y][r-z]>d[x][r]) d[y][r-z]=d[x][r],q.push((node){d[y][r-z],y,r-z});
			}
		}
		while(q.size()) q.pop();
		if(!flag) puts("impossible");
	}
	return 0;
}