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 pop 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,

1.. Am I misunderstand SPFA?

1. 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 :)