### b06b01073's blog

By b06b01073, history, 4 days ago,

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,

1. Am I misunderstand SPFA?

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

• +19

 » 4 days ago, # |   0 Auto comment: topic has been updated by b06b01073 (previous revision, new revision, compare).
 » 4 days ago, # |   0 Auto comment: topic has been updated by b06b01073 (previous revision, new revision, compare).
 » 4 days ago, # |   -7 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
•  » » 4 days ago, # ^ |   +5 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?
•  » » 4 days ago, # ^ |   +7 the complier will Optimize your following code  long long cnt = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ for(int _k = 0; _k < n; _k++){ cnt++; } } } the above code will run in $O(1)$ if you add -O2 parameter
 » 4 days ago, # |   0 Auto comment: topic has been updated by b06b01073 (previous revision, new revision, compare).
 » 4 days ago, # |   0 the time complex of SPFA is $O(|V||E|)$ (the same as Bellman-Ford)
•  » » 4 days ago, # ^ |   0 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.
 » 4 days ago, # | ← Rev. 5 →   +29 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.
•  » » 4 days ago, # ^ |   0 As you mentioned, $O(|E|)$ is the average time 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.
•  » » » 4 days ago, # ^ | ← Rev. 2 →   0 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).