Hello codeforces community, ↵
I recently run in to a problem [D. Okabe and City](https://mirror.codeforces.com/contest/821/problem/D), someone use shortest path algorithm to solve this problem, which is SPFA to be more specifically.↵
↵
And here is the [code](https://blog.csdn.net/lyg_air/article/details/77163091) 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](https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm), 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](https://mirror.codeforces.com/contest/821/submission/108346392)(the code is the same as above) and get accepted.↵
↵
My questions are,↵
↵
1.. Am I misunderstand SPFA?↵
↵
2. 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 :)↵
I recently run in to a problem [D. Okabe and City](https://mirror.codeforces.com/contest/821/problem/D), someone use shortest path algorithm to solve this problem, which is SPFA to be more specifically.↵
↵
And here is the [code](https://blog.csdn.net/lyg_air/article/details/77163091) 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](https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm), 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](https://mirror.codeforces.com/contest/821/submission/108346392)(the code is the same as above) and get accepted.↵
↵
My questions are,↵
↵
1.
↵
2. 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 :)↵
