SPFA算法

负环P3385: https://www.luogu.com.cn/problem/P3385

SPFA视频: https://www.bilibili.com/video/BV19mq4BREGL

这种一个测试点多个测试数据的，一定要每次清空数组!

memset(dis, 0x3f3f3f3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
memset(inwait, 0 ,sizeof(inwait)); // 清空是否在队中
for (int k = 1; k <= n; k++) a[k].clear(); // 清空邻接表
while (!q.empty()) q.pop();  // 清空队列

注意，如果某个定点已经在队列中，不能重复加入队列，所以设定一个数组判断顶点是否在队列中。

// 主要程序
while (!q.empty()) {
	int u = q.front();q.pop();
		
	inwait[u] = 0;
	vis[u]++;
	if (vis[u] > n) {
		// 一个点连续入队超过n次，证明存在负环
		break;
	}
	// 遍历u所能到达的点	
	for (auto ed : a[u]) {
		if (dis[ed.v] > ed.w + dis[u]) {
			dis[ed.v] = ed.w + dis[u];  // 1到达上一个点的距离dis[u]加上当前边的权重ed.w
			if (!inwait[ed.v]) { 
				inwait[ed.v] = 1;
				q.push(ed.v);
			}
					
		}
				
	}
}