public static boolean spfa(int n) {
distance[1] = 0;
queue[r++] = 1;
entered[1] = true;
updatedCount[1]++;
while (l < r) {
int u = queue[l++];
entered[u] = false;
for (int ei = head[u], v, w; ei > 0; ei = next[ei]) {
v = to[ei];
w = weight[ei];
if (distance[u] + w < distance[v]) {
distance[v] = distance[u] + w;
if (!entered[v]) {
if (++updatedCount[v] == n) {
return true;
}
queue[r++] = v;
entered[v] = true;
}
}
}
}
return false;
}
