b06b01073's blog

By b06b01073, history, 45 hours ago, In English

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

 
 
 
 
  • Vote: I like it
  • +19
  • Vote: I do not like it

»
45 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by b06b01073 (previous revision, new revision, compare).

»
45 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by b06b01073 (previous revision, new revision, compare).

»
39 hours ago, # |
  Vote: I like it -7 Vote: I do not like it

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

  • »
    »
    38 hours ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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?

  • »
    »
    38 hours ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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

»
38 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by b06b01073 (previous revision, new revision, compare).

»
38 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

the time complex of SPFA is $$$O(|V||E|)$$$ (the same as Bellman-Ford)

  • »
    »
    38 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
38 hours ago, # |
Rev. 5   Vote: I like it +29 Vote: I do not like it

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.

  • »
    »
    37 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.