用原来最短路的模板改了改后的spfa水过了该题

然鹅一看讨论区发现有重边

再一看自己的程序，没有判重边的部分

难道是spfa具有重边免疫力吗

祝愿我比赛的时候也有这样的免疫力

言归正传，原理是什么a

# include <cstdio>
# include <cstring>
# include <queue>
using namespace std;
int n,p,a,b,c,lk[66666],vis[66666],dis[66666],hp;
queue < int > q;
struct sth{
	int p,o,w;
}e[166666];
void add(int u,int v,int t)
{
	e[++hp] = {v,lk[u],t};
	lk[u] = hp;
}
void spfa()
{
	vis[1] = 1,q.push(1),dis[1] = 0;
	while (!q.empty())
	{
		int x = q.front();q.pop();vis[x] = 0;
		for (int i = lk[x];i;i = e[i].o)
		{
			if (dis[x] + e[i].w < dis[e[i].p])
			{
				dis[e[i].p] = dis[x] + e[i].w;
				if (!vis[e[i].p]) q.push(e[i].p),vis[e[i].p] = 1; 
			}
		}
	}
}
int main()
{
	memset(dis,0x3f,sizeof(dis));
	scanf("%d %d",&n,&p);
	for (int i = 1;i <= p;i++)
	{
		scanf("%d %d %d",&a,&b,&c);
		add(a,b,-c);
	}
	spfa();
	if (dis[n] == 0x3f3f3f3f) printf("-1");
	else printf("%d",-dis[n]);
}