深入浅出代码长这样，用链式前向星改写后（spfa部分）：

bool spfa(){
	queue<int> Q;
	for(int i = 1;i <= n;i++){
		dis[i] = inf;
		vis[i] = 0;
	}
	Q.push(0);
	dis[0] = 0,vis[0] = 1,sum[0] = 1;
	while(!Q.empty()){
		int u = Q.front();
		Q.pop();
		vis[u] = 0;
		for(int i = h[u];i;i = nxt[i]){
			int v = to[i];
			if(dis[v] > dis[u] + val[i]){
				dis[v] = dis[u] + val[i];
				if(vis[v] == 0){
					vis[v] = 1;
					Q.push(v);
					sum[v]++;
					if(sum[v] > n + 1) return 1;
				}
			}
		}
	}
	return 0;
}

但是只有37pts，改成这样：

bool spfa(){
	queue<int> Q;
	for(int i = 1;i <= n;i++){
		dis[i] = inf;
		vis[i] = 0;
	}
	Q.push(0);
	dis[0] = 0,vis[0] = 1,sum[0] = 1;
	while(!Q.empty()){
		int u = Q.front();
		Q.pop();
		vis[u] = 0;
		for(int i = h[u];i;i = nxt[i]){
			int v = to[i];
			if(dis[v] > dis[u] + val[i]){
				dis[v] = dis[u] + val[i];
				if(vis[v] == 0){
					vis[v] = 1;
					Q.push(v);
					sum[v]++;
					if(sum[v] > n) return 1;
				}
			}
		}
	}
	return 0;
}

把 $n+1$ 改成 $n$ 就AC了，为什么？