#include <iostream>
#include <algorithm>
#include <queue>
#include <stdio.h>
#include <string.h>
		  /*#include <stack>*/

		  using namespace std;
#define EMAX 20010
#define VMAX 1010
#define inf ((1ll<<60) - 1)

int F[VMAX];
int c;

struct graph
{
	struct edge
	{
		int c;
		int v;
		int next;
		/*		int interaction;*/
	};
	edge buf[EMAX];int e;
	int point[VMAX];int n;

	graph()
	{
		memset(point,-1,sizeof(point));
		e = 0;
	}

	void add_edge(int u,int v,int c)
	{
		buf[e].v = v;
		buf[e].next = point[u];
		point[u] = e;
		buf[e].c = c;
		e++;
	}
};


long long dis[VMAX][101];
struct SPFA:graph
{

	struct node
	{
		int u,c;
// 		int len;
// 		bool operator<(const node &b)const
// 		{
// 			return len > b.len;
// 		}
	};

	bool spfa(int s,int t)
	{
		int i;
				bool visit[VMAX][101];
		// 		int times[VMAX][101];
		for(i = 0; i < n; i++)
		{
			int j;
			for(j = 0; j <= c; j++)
				dis[i][j] = inf;visit[i][j] = true;/*times[i][j] = 0;*/
		}
		/*priority_*/queue<node> q;
		dis[s][0] = 0;visit[s][0] = false;/*times[s][0] = 1;*/
		node temp;
		temp.u = s;
		temp.c = 0;
/*		temp.len = 0;*/
		q.push(temp);
		while(!q.empty())
		{
			node tmp = q.front();
			q.pop();
			visit[tmp.u][tmp.c] = true;
/*			if(tmp.u == t) return true;*/
/*			if(tmp.len > dis[tmp.u][tmp.c]) continue;*/

			/*visit[tmp.u][tmp.c] = true;*/
			int p = point[tmp.u];
			while(p != -1)
			{
				if(tmp.c < buf[p].c){p = buf[p].next;continue;}
				node temp;
				temp.u = buf[p].v;
				temp.c = tmp.c - buf[p].c;
				if(dis[temp.u][temp.c] > dis[tmp.u][tmp.c])
				{
					dis[temp.u][temp.c] = dis[tmp.u][tmp.c];
	/*				temp.len = dis[temp.u][temp.c];*/
					if(visit[temp.u][temp.c])
					{
						visit[temp.u][temp.c] = false;
						q.push(temp);
					}
				}
				p = buf[p].next;
			}
			if(tmp.c < c && dis[tmp.u][tmp.c+1] > dis[tmp.u][tmp.c] + F[tmp.u])
			{
				dis[tmp.u][tmp.c+1] = dis[tmp.u][tmp.c] + F[tmp.u];
				node temp;
				temp.u = tmp.u;
				temp.c = tmp.c + 1;
				/*				temp.len = dis[temp.u][temp.c];*/
				if(visit[temp.u][temp.c])
				{
					visit[temp.u][temp.c] = false;
					q.push(temp);
				}
			}
		}
		return true;
	}

};

SPFA g;

int main()
{

	int m;
	scanf("%d%d",&g.n,&m);
	int i;
	for(i = 0; i < g.n; i++) scanf("%d",&F[i]);
	for(i = 0; i < m; i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		g.add_edge(x,y,z);
		g.add_edge(y,x,z);
	}
	int q;
	scanf("%d",&q);
	while(q--)
	{
		int s,t;
		scanf("%d%d%d",&c,&s,&t);
		g.spfa(s,t);
		if(dis[t][0] < inf) printf("%lld\n",dis[t][0]);
		else printf("impossible\n");
	}


}

• Re:spfa 为何就错了呢，那位闲的慌的大牛帮看看！！（附：spfa-dijkstra 用优先堆已过，但队列实现一直错） (2552) 1362256953 2023-04-26 15:16:36
  • Re:spfa 为何就错了呢，那位闲的慌的大牛帮看看！！（附：spfa-dijkstra 用优先堆已过，但队列实现一直错） (27) 1362256953 2023-04-26 15:17:57