`Algorithm-Solution` `AcWing` 920. 最优乘车

link

Solution

This question is quite abstract if you not transform it to a graph.
The notion Bus-Transfer is a little awkward, so we use Bus-Total which is one greater than the former. (e.g., we take buses $A,B,C$, then Bus-Total = Bus-Transfer + 1 = 3)

The route of a bus has at most $n$ stations.

There is an important point that a route $a\to b\to c$ (because the bus is One-Directional), so $a$ can arrive to $b$ but inverse is not.

---

If we handle it in a brute direct way, $Dist[a][b]$ means the minimal Bus-Total from $a$ to $b$.
If we are currently at Bus-i, then $Dist[a][b]$ means the minimal Bus-Total from $a$ to $b$ under using those Buses 0, ..., i-1.
Suppose the route of current Bus-i is $a1,a2,a3,a4$, it means $ai$ can arrive to $aj$ where $j>i$.
so for every $ai,aj$, update $x\to ai-aj\to y$ Dist[ x][ y] = min( self, Dist[ x][ ai] + 1 + Dist[ aj][ y])

void __Solve( int _test_id){
    ( void)_test_id;
    //--
    int n, m;
    cin >> m >> n;
    getchar();
    memset( D, 0x3F, sizeof( D));
    for( int i = 0; i < m; ++i){
        string s;
        getline( cin, s);
        stringstream ss( s);
        int a;
        M = 0;
        while( ss >> a){
            -- a;
            A[ M ++] = a;
        }
        for( int j = 0; j < M - 1; ++j){
            for( int z = j + 1; z < M; ++z){
                int a = A[ j], b = A[ z];
                for( int p = 0; p < n; ++p){
                    for( int s = 0; s < n; ++s){
                        int l = D[ p][ a];
                        int r = D[ b][ s];
                        if( p == a){ l = 0;}
                        if( s == b){ r = 0;}
                        D[ p][ s] = min( D[ p][ s], l + r + 1);
                    }
                }
            }
        }
        for( int j = 0; j < M - 1; ++j){
            for( int z = j + 1; z < M; ++z){
                D[ A[ j]][ A[ z]] = 1;
            }
        }
    }
    if( D[ 0][ n - 1] > m){
        cout << "NO";
        return;
    }
    cout << D[ 0][ n - 1] - 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

But this is Out-Of-Time $O(n^4\ast m)$

---

To transform a graph question into a specific graph is vital, because graph-question is usually very abstract, hard to comprehend.

First step:
We consider what information a route of a bus $a1,a2,a3,a4$ expresses.
The all meanings of such a route is that, $ai$ can reach $aj$ where $j>i$.
So suppose we have a directed unweighted graph G, then this route shows that there is a edge from $ai$ to $aj$.
Conversely, for any edge $a\to b$ in G, it implies that there has a bus that could take $a$ to $b$.

Second step:
Then, we consider the meaning of Bus-Transfer.
Two routes of Bus($a,b$) are $a1,...,a5,a6,...$ and $b1,...,b5,b6,...$ (where $a5=b5$)
If we currently at Bus-a, and get off at $a_5$ then we can get on Bus-b at $b_5$.
The essence of Bus-Transfer is actually a point which is contained by two routes.
The counterpart of this notion to the graph is:

• $ai$ (where $i\le 5$) can reach $bj$ (where $j\ge 5$)
• $bi$ (where $i\le 5$) can reach $aj$ (where $j\ge 5$)

For the graph G constructed by First-Step rule, we found $G$ has already possess the property of Bus-Transfer. (because there are paths $ai\to a5\to bj$ and $bi\to b5\to aj$ where $i<5,j>5$)
So, we need not to add extra information to the graph at this step.

Third Step:
What is the meaning of minimal Bus-Total?
In the graph, a path $a\to b\to c$ consists of two edges $a\to b$ and $b\to c$ means that, there is a bus can take $a$ to $b$ and a bus that take $b$ to $c$. (these two buses maybe a same bus)
So the choices of $a\to b$ correspond to several paths in the graph, a path is a scheme that take $a$ to $b$, the length of the path (the count of edges) means the Bus-Total of this scheme.

So, let all edges in the graph to have a weight $1$, then find the minimal-path in the graph (it can be solved by BFS)