Hello codeforces community, I recently run in to a problem D. Okabe and City, someone use shortest path algorithm to solve this problem, which is SPFA to be more specifically.

And here is the code from https://blog.csdn.net/lyg_air/article/details/77163091.

```
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
const int MX = 1e4 + 5;
int n, m, k;
struct node{
int x, y;
}lit[MX];
int dis[MX];
int inq[MX];
int spfa(){
for(int i = 1; i <= k; i++){
dis[i] = INF;
}
queue<int> q;
q.push(1);
inq[1] = 1;
dis[1] = 0;
while(!q.empty()){
int u = q.front();
q.pop();
inq[u] = 0;
for(int i = 1; i <= k; i++){
if(u == i) continue;
int val = INF;
int dx = abs(lit[u].x - lit[i].x);
int dy = abs(lit[u].y - lit[i].y);
if(dx+dy == 1){
val = 0;
}
else if(dx <= 2 || dy <= 2){
val = 1;
}
if(dis[i] > dis[u] + val){
dis[i] = dis[u] + val;
if(!inq[i]){
q.push(i);
inq[i] = 1;
}
}
}
}
if(dis[k] != INF) return dis[k];
return -1;
}
int main(){
scanf("%d%d%d", &n, &m, &k);
int flag = 0;
for(int i = 1; i <= k; i++){
int u, v;
scanf("%d%d", &lit[i].x, &lit[i].y);
if(lit[i].x == n && lit[i].y == m) flag = 1;
}
if(!flag){
lit[++k].x = n+1;
lit[k].y = m+1;
}
cout << spfa() << endl;
return 0;
}
```

In this code, it treats all the initially lit positions as a vertice and try to calculate the shortest path to the bottom-right corner using SPFA.

The worst case of SPFA is $$$O(|V||E|)$$$ according to wiki, and in the `for`

loop inside the `spfa`

function, it seems this code treat the graph as a complete graph(since for every vertice popped from the queue, it consider all other $$$k - 1$$$ vertices, where $$$k$$$ is the number of vertices), which make $$$O(|E|) = O(|V|^2)$$$, and the overall time complexity will turn into $$$O(|V|^3)$$$.

In this problem, $$$k \leq 10^4$$$, which doesn't look promising for a 4 seconds time limit, however this code only take 529ms in this submission(the code is the same as above) and get accepted.

My questions are,

Am I misunderstand SPFA?

Is my analysis of the $$$O(|V|^3)$$$ time complexity is totally wrong

Please let me know if my question is unclear, and thanks for all your help :)

Auto comment: topic has been updated by b06b01073 (previous revision, new revision, compare).Auto comment: topic has been updated by b06b01073 (previous revision, new revision, compare).Even I'm confused. I thought test cases were weak but when I checked n,m,k, they were all around $$$10^4$$$. So I added a variable

`cnt`

in your code to count the number of operations. Can anyone explain how`cnt`

is`3000000000000`

without submission giving TLE.Submission

lol, that's what I am confused about.

But do you think the time complexity analysis part($$$O(|V|^3)$$$) is correct by the way?

the complier will Optimize your following code

the above code will run in $$$O(1)$$$ if you add

`-O2`

parameterAuto comment: topic has been updated by b06b01073 (previous revision, new revision, compare).the time complex of SPFA is $$$O(|V||E|)$$$ (the same as Bellman-Ford)

But it seems like this code treat the graph as a complete graph which make $$$|E| = \frac{|V|\times (|V| - 1)}{2} = O(|V|^2)$$$, so $$$O(|V||E|)$$$ is actually $$$O(|V|^3)$$$ in worst case.

The name of the algorithm is "Shortest Path Faster Algorithm", and the "Faster" in the name is not without reason. This algorithm is executed in $$$O(|E|)$$$ in the average case in random graphs.

Now, there may be two causes for you not to receive TLE.

The first is that the tests are weak. This is possible because a special graph is needed to provide the worst case of the SPFA.

The second is that can be impossible to produce a special graph that respects the entry restrictions. Since all edges have binary weight.

As you mentioned, $$$O(|E|)$$$ is the

averagetime complexity, but aren't we suppose to use a tight worst case upperbound to make sure the algorithm will not receive TLE?(at least in the contest, even if I come up with this algorithm, I will think it is impossible to pass).But I do think the two scenario you mentioned are probably the case why I'm not receiving TLE.

Thanks for your opinion.

The intuition says that the standard upper bound is very bad for binary weight, but I have no idea how to prove something better.

Anyway, it has an algorithm similar to SPFA in this case where the weights are binary. This is called 0-1 BFS that runs in $$$O(E)$$$. The difference for SPFA is that if the edge weight is 0, then it is pushed to the front of the priority queue (which in this case is a deque).

Submission: https://codeforces.com/contest/821/submission/108384857

Reference: https://cp-algorithms.com/graph/01_bfs.html