`Algorithm-Solution` `AcWing` 342. 道路与航线

link

Solution

Given a graph $G$ which contains two types of edges:
+ $E1(a,b,w)$ means there is a undirected edge with a weight $w\ge 0$ between $a,b$.
+ $E2(a,b,w$) means a directed edge from $a$ to $b$ with a weight $w\in N$ (maybe negative)

And a property on $E2(a,b,w)$: there is no path (consists of $E1,E2$) that from $b$ to $a$. Property-1

This property is pivotal, it shows that $G$ is a special kind of DAG.
+ Firstly, we divide $G$ into several set according to $E1$, let it be $S1,S2,S3,...$ (any two points are accessible for each other in a set, but any two points are not connected if they are not in a same set).
If we suppose $S1,...$ are also points, then you will get a graph $GS$ which has no edge.
+ Secondly, for a edge $E2(a,b,w)$ then we connect a directed edge from $a$ to $b$, so now, $GS$ becomes a DAG (according to Property-1) (although the direct information by the question is, if $E2(a,b)$ then no path from $b$ to $a$, it also indicates that there is no path from $x$ to $y$ where $b\to x$ and $y\to a$.)

Given a start-point S. calculate the shortest-distance of $S\to x$ where $x$ is any point of $G$.

The answer is unique (either no-path from $S$ to $x$, or there exists a shortest-distance) although there exist negative-edge in $G$.
But, because all negative-edges form a DAG, so in fact, there is no negative-loop in $G$.

         |----------------|
         |                v
S5------>S1----->S2------>S4
         |                ^
         |------>S3-------|
S6
1
2
3
4
5
6

Every set $Si$ is a undirected, non-negative-weighted, connected graph

Suppose $S\in S1$
+ For any set that is not accessible for $S1$, any point in such sets is No-Path for $S$.
+ For any point in $S1$, it can be solved by Dijkstra only acted in $S1$.
+ For these accessible sets $S2,S3,...$, they are all solvable.
... (there is one thing to clarify, $S1\to S2$ not means a edge between two sets, e.g. $S1=(a,b,S),S2=(d,e,f)$ and edges $(a-d)(b-e)$, so $S1\to S2$ actually denotes a set of edges with origin-point in $S1$ and destiny-point in $S2$)
We get its Topological-Sequence (S1, S2, S3, S4)
++ Firstly iterate to $S1$ according to the Topo-Sequence, after the operation $Dijk(S1)$, now we have $S1$ is correct (that is, the answer for any point in $S1$ is determined), then use $S1$ and all adjacent-edges to update the outside-points, more precise, (for any edge $(a,b,w)$ in $E2$ where $a\in S1,$ $b\in S2/S3/..$, perform $Dist[b]=min(self,Dist[a]+w)$, notice that $Dist[a]$ is correct at present)
++ Secondly iterate to $S2$ according to the Topo-Sequence, after the operation $Dijk(S2)$ (here it differs from $Dijk(S1)$ which is the standard-Dijkstra-from that has a start-point $S$ with $Dist[S]=0,Dist[others]=Infinity$, but the start-point in here is all points in $S2$ whose $Dist\ne Infinity$, i.e., it has multiple start-points), we need to prove that $S2$ is correct now after $Dijk(S2)$ (once we proved it, then all $Si$ are correct)
More generally, the Topo-Sequence $S1,S2,...,Si$ (all $S1,...,S_{i-1}$ are correct), prove $Si$ is correct after $Dijk(Si)$
For any point $a\in Si$, the shortest-path of $a$ is of the form $...,a$ ($...$ must belongs to $S1/.../Si$), let $b$ be the point that satisfies $c1,b,c2,a$ where $c1$ are all not belong to $Si$ and $b,c2,a$ are all belong to $Si$.
(1) If $b=a$, that is $...,c,a$ (suppose $c$ belongs to $Sj$), $Dist[a]=Dist[c]+(c-a)$, it will be performed in $Sj$ with $Dist[c]$ is correct. So $Dist[a]$ is already correct even if before the performance of $Dijk(Si)$.
(2) if $b\ne a$, that is $...,c,b,...,a$, now $Dist[b]$ is correct (according to the above-(1)), $b$ is a start-point of $Dijk(Si)$ and all edges in $b,...,a$ are non-negative, ($b,...,a$ must be the shortest-path in $Si$)
Although $Dist[a]=Dist[b]+Dist[b\to a]$ where $Dist[b]$ maybe negative, $Dijk(Si)$ just focuses on $Si$ where all edges are non-negative in the graph, in the other words, $Dijk(Si)$ is used to solve $Dist[b\to a]$ which is non-negative (not involves the negative $Dist[b]$, because $Dist[b]$ is correct, it will be viewed as a start-point which be putted into the heap of Dijkstra originally; it’s important to realize that, the distance of start-point can be any number not necessary be $0$ as usual, so as provide that all edges are non-negative in the graph, Dijkstra is also valid; e.g., if $Dist[s]=0$ then you will get $Dist[e]=x$ after Dijkstra, you will get $Dist[e]=x+y$ if you set $Dist[s]=y$)
... One another thing is that, not all start-points (whose $Dist[]\ne Infinity$) are correct, e.g., a start-point whose shortest-path is the case-(2) as discussed above.
But $s$ must be correct, if $s$ has the least-$Dist$ among other start-points, that is, after we put all start-points into the heap, its top-element must be correct. Maybe the second-top-element is also correct (i.e., its $Dist$ will never be updated in the process of $Dijk$), also maybe not.

---

After $Dijk(Si)$, $Si$ is correct; next step, we will update $Sj$ using $E2$ (we called this process Update-Next).
In fact, Update-Next can be done in the Dijk-process; because when a element $c$ firstly out of heap, its $Dist$ is correct, so when it updates successfully $Dist$ in Dijkstra $c\to d$, we check if $d$ is also in $Si$ then put it into heap as the usual process that Dijkstra do, otherwise $d$ belongs to a another $Sj$, then do not put it into heap, just update $d$ is enough which means the process Update-Next.

Code

class Dijkstra{
	void Initialize( int _start){
        memset( ptr_distance, 0x7F, sizeof( _Distance_Type) * ptrRef_graph->Get_pointsCount());
        memset( ptr_isFirstTime, true, sizeof( bool) * ptrRef_graph->Get_pointsCount());
        ptr_distance[ _start] = 0;
    }
    void Work( int _set_id){
        while( false == heap.empty()){
            heap.pop();
        }
        //--
        for( auto i : Set[ _set_id]){
            if( ptr_distance[ i] != 0x7F7F7F7F){
                heap.push( make_pair( ptr_distance[ i], i));
            }
        }
        int cur, nex, edge;
        while( false == heap.empty()){
            cur = heap.top().second;
            heap.pop();
            if( false == ptr_isFirstTime[ cur]){
                continue;
            }
            ptr_isFirstTime[ cur] = false;
            for( edge = ptrRef_graph->Head[ cur]; ~edge; edge = ptrRef_graph->Next[ edge]){
                nex = ptrRef_graph->Vertex[ edge];
                if( ptr_distance[ cur] + ptrRef_graph->Weight[ edge] < ptr_distance[ nex]){
                    ptr_distance[ nex] = ptr_distance[ cur] + ptrRef_graph->Weight[ edge];
                    if( Set_id[ nex] == Set_id[ cur]){
                        heap.push( make_pair( ptr_distance[ nex], nex));
                    }
                }
            }
        }
    }
};

void __Solve( int _test_id){
    ( void)_test_id;
    //--
    int T, R, P, S;
    scanf("%d%d%d%d", &T, &R, &P, &S);
    -- S;
    Graph_Weighted< int> g( T, 2 * R + P);
    g.Initialize( T);
    DisjointSet d( T);
    d.Initialize( T);
    memset( Set_id, -1, sizeof( Set_id));
    int set_count = 0;
    for( int i = 0; i < R; ++i){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        -- a, -- b;
        g.Add_edge( a, b, w);
        g.Add_edge( b, a, w);
        d.Merge( a, b);
    }
    for( int i = 0; i < T; ++i){
        if( d.Is_root( i)){
            Set_id[ i] = set_count;
            ++ set_count;
        }
    }
    for( int i = 0; i < T; ++i){
        Set_id[ i] = Set_id[ d.Get_root( i)];
    }
    for( int i = 0; i < T; ++i){
        if( Set_id[ i] == -1){
            Set_id[ i] = set_count;
            ++ set_count;
        }
    }
    for( int i = 0; i < T; ++i){
        Set[ Set_id[ i]].push_back( i);
    }
    Graph_UnWeighted set_g( set_count, P);
    set_g.Initialize( set_count);
    for( int i = 0; i < P; ++i){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        -- a, -- b;
        g.Add_edge( a, b, w);
        ASSERT_( Set_id[ a] != Set_id[ b]);
        set_g.Add_edge( Set_id[ a], Set_id[ b]);
    }
    Topological_Sequence t( &set_g);
    bool ttt = t.Work();
    ASSERT_( ttt);
    Dijkstra< int, int> dijk( &g);
    dijk.Initialize( S);
    for( int i = 0; i < set_count; ++i){
        dijk.Work( t.Sequence[ i]);
    }
    for( int i = 0; i < T; ++i){
        if( dijk.Distance[ i] == 0x7F7F7F7F){
            printf("NO PATH\n");
        }
        else{
            printf("%d\n", dijk.Distance[ i]);
        }
    }
}
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102