Introduction

The programme is aimed to simulate the management of a public bike service. Once a station is empty or full, it must be adjust to the perfect condition, so as all the other stations on the way from PBMC to the problem station.
To choose a best path, we need to consider the following three factors: distance, number of bikes sent from PBMC and number of those sent back. Their priorities are in a descending order in our consideration.
Generally the problem can be seen as an upgraded shortest path problem.

Algorithm Specification

First we need to store the edge value. For each station, we use a linked list(a[ ]) to store the value of all its edges, and then another linked list(first[ ])to store the head of every node’s edge list.
u, v and w are three variables appear in each of the N lines. We use fuction push to build a single directed edge and function AddEdge to build an undirected edge.

Store Edge Value

function push(const int& u, const int& v, const int& w)
    set a[e].v as v;
    set a[e].w as w;
    set a[e].next as first[u];
    set first[u] as e++;  

function AddEdge(const int& u, const int& v, const int& w)  
    push(u, v, w);
    push(v, u, w);

Function AddEdge is called N times since there are N edges.

Definition of struct Value

struct Value{
    int dis, take, now;
    Value(); 
    bool operator < (const Value& x) const ;
    }

Struct Value contains three factors we need to choose the best path.

Reload operator <
Since we need to make some comparison while deciding the best path, all the three factors mentioned before must be considered according to their priorities. Here we reload operator < to simplify our coding. After that we can directly judge between two stations to update our best solution.

Reload operator < 
    if dis eq. x.dis
        if take eq. x.take
            return now < x.now;
        else 
            return take < x.take
    return dis < x.dis;

As we can see, dis is the factor we give thought to in the first place, followed by take and now.

Dijkstra Algorithm
On the basis of all the work we have done, we can now adapt Dijkstra’s Algorithm to finally complete our job. But before that we must prove the feasibility of the idea.
It is crucial that all the edge values are positive. To illustrate the point, let’s look at an example. Once we have decided $dis_u$ = $dis_v$, then the conclusion is fixed and no extra adjustment shall be made later. That is to say, even if there is another way from u to v, it’s definitely true that $dis_v$+W > $dis_u$ because W is always positive. Thus, whatever the situation, $dis_u$ is still the shorter one.

void Solver()  {
    dis[0].dis = 0;                        
    Value tmp; int id;                          
    for (int T = 0; T <= n; ++T) {          
        tmp.dis = Inf;                      
        for (int i = 0; i <= n; ++i)          
            if (!vis[i] && dis[i] < tmp)       
                tmp = dis[i], id = i; 
        
        vis[id] = true;                     
        for (int i = first[id]; i; i = a[i].next) {
            tmp.dis = dis[id].dis + a[i].w;        

            if (dis[id].now + bike_num[a[i].v] < 0) 
                tmp.take = dis[id].take - bike_num[a[i].v] - dis[id].now, tmp.now = 0;
            else tmp.now = dis[id].now + bike_num[a[i].v], tmp.take = dis[id].take;

            if (tmp < dis[a[i].v])  
                dis[a[i].v] = tmp, prev[a[i].v] = id;  
        }
    }
}

N is the number of nodes and E is the number of edges. We can see that there is a double-nested loop, so the time complexity of the algorithm is $O(N^2+E)$. The space complexity is $O(N+E)$.

Function Print
Finally we use recursion to output the result.

Print(int x, bool opt)   
    if (!x) return printf("0->"), void();
    Print(prev[x], true);
    printf("%d", x);
    printf(opt ? "->" : " ");

Testing Results

Case 1:

100 7 7 9
30 40 70 70 40 30 0
0 1 2
0 2 2
0 3 2
1 4 2
2 5 1
3 6 2
4 7 2
5 7 1
6 7 2

A random case to test if the programme is able to work properly.
The expected output is 70 0->2->5->7 0.
Program output is 70 0->2->5->7 0.
Status: Pass.

Case 2:

A random case to test if the programme is able to work properly.
The expected output is 3 0->1->4 0.
Program output is 3 0->1->4 0.
Status: Pass.

Case 3:

10 7 7 8
3 3 8 8 8 9 0
0 1 3
0 2 6
1 3 4
2 4 1
3 5 3
4 6 2
5 7 1
6 7 2

A special case to test if the programme can output the path that requires minimum number of bikes taken back.
The expected output is 2 0->1->3->5->7 1.
Program output is 2 0->1->3->5->7 1.
Status: Pass.

Case 4:

A random case to test if the programme is able to work properly(only back).
The expected output is 0 0->2->4 5.
Program output is 0 0->2->4 5.
Status: Pass.

Analysis and Comments

Now we have get a $O(N^2+E)$ algorithm. However, we can do better.
Noticed that we use a for loop to find the best unvisited node. Its time complexity is $O(N)$. We can use heap to optimize it.
If a node doesn’t in the heap, it’s easy. We just push it and its value into the heap. But what if it’s in the heap? We still push it and its value into the heap if this node have better value. Because we will first get this node with better value and we just need to judge if the node pop from heap is visited. Thus, we optimize this process to $O(logN)$. But this project’s N will not be bigger than 500, we can use $O(N^2+E)$ algorithm to solve this problem.
And maybe we can solve this problem in another way. After we find the shortest path, the path will not contain cycles and we will get a DAG. Then we can use top sort to find Answer. Its time complexity is still $O(N^2+E)$ for we still need to find the shortest path.

Declaration
We hereby declare that all the work done in this project titled
“Public Bike Management” is of our independent effort as a group.