>
> #include <iostream>
> #include <算法>
> #include <队列>
> #include <stdio.h>
> #include <字符串.h>
> /*#include <堆栈>*/
>
使用命名空间 std >;
> #define EMAX 20010
> #define VMAX 1010
> #define INF （（1ll<<60） - 1）
>
> int F[VMAX];
> 国际 c;
>
>结构图
> {
>结构边缘
> {
> 国际 c;
> int v;
> int 下一个;
> /* int interaction;*/
> };
> edge buf[EMAX];int e;
> int point[VMAX];int n;
>
>图（）
> {
> 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];
>点[u] = e;
> buf[e].c = c;
> e++;
> }
> };
>
>
> 长长 dis[VMAX][101];
>结构 SPFA：图形
> {
>
>结构节点
> {
> int u，c;
> // int len;
> // bool operator<（const node &b）const
> // {
> // 返回 len > b.len;
> // }
> };
>
> bool spfa（int s，int t）
> {
> int i;
>布尔访问[VMAX][101];
> // int times[VMAX][101];
> for（i = 0; i < n; i++）
> {
> 国际 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;*/
>节点温度;
> 温度 u = s;
>温度 c = 0;
> /* temp.len = 0;*/
> q.push（temp）;
> while（！q.empty（））
> {
>节点 tmp = q.front（）;
> q.pop（）;
> visit[tmp.u][tmp.c] = true;
> /* if（tmp.u == t） 返回 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;}
>节点温度;
> 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]）
> {
> 访问[temp.u][temp.c] = 假;
> 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];
>节点温度;
> temp.u = tmp.u;
> 温度 c = tmp.c + 1;
> /* temp.len = dis[temp.u][temp.c];*/
> if（visit[temp.u][temp.c]）
> {
> 访问[temp.u][temp.c] = 假;
> q.push（temp）;
> }
> }
> }
>返回 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 用优先堆已过，但队列实现一直错） (27) 1362256953 2023-04-26 15:17:57