天梯L3 007 天梯地图

Posted on | Edited on | In | Comments:
Dijstra最短路变形

题目

输入示例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
5 4 0 2 3
5 9 1 1 4
0 6 0 1 1
7 3 1 1 2
8 3 1 1 2
2 5 0 2 2
2 1 1 1 1
1 5 0 1 3
1 4 0 1 1
9 7 1 1 3
3 1 0 2 5
6 3 1 2 1
5 3

输出示例一

1
2
Time = 6: 5 => 4 => 8 => 3
Distance = 3: 5 => 1 => 3

输入示例二

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

输出示例二

1
Time = 3; Distance = 4: 3 => 2 => 5

Dijstra算法

  • bfs+优先队列其实就是dijstra算法
  • dijstra维护result set，源节点到这个set里的点的最短路径已经找到，所以result set只会有node被加进去而不会有node被踢出去
  • 不同于算法导论描述的dijstra算法——算导里的堆是点的堆，所以当发现有新的路径可以以更小的代价到达某点时（该点之前已经在堆里），会使用堆decrease key操作——把这个点的权值减低，并且调整堆使得堆合法。但是stl的优先队列并没有decrease key的操作，所以使用另一种实现——允许某点多次加入到优先队列里——其实就等价于优先队列里放Edge。所以在从优先队列里pop出最小权的点时，要判断该点是否已经处于result set里。这样做会使得复杂度从$O((E+V)lgV)$ 变为$O(ElgE)$

Dijstra找出所有最短路径

  • 从src到dest的路径上的某些节点有多种到达方法——这就导致了多条路径。所以我们要维护所有节点的parent list——无论从哪个parent 到这个节点都是最短的。
  • 具体实现是：从优先队列其pop出某节点，该节点已经处于result set里，但是源节点到该节点的代价与result中的这个节点的路径代价相同，那么这条新的路径就是另一个条到达这个节点的路径。使用一个vector来存储某个节点的parent list——比如vector<int> parent[600] ，则parent[n] 代表的vector就是编号为n的节点的parent list
  • 然后使用dfs去计算所有可能的路径的另外一种代价——比如此题，以时间为权重的最短路径有多条，但是我们还需要计算出这些路径在使用路径长度作为权重时该路径的代价。这一步可以使用记忆化搜索。

需要注意的点

不可以这样寻找同代价的不同parent 节点

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    // 参数me是该edge的终点，p是该edge的起点，t出发的源节点到这条edge的终点的代价
    // 其实edge t就代表了节点me
    struct Edge_t {
        int me;
        int p;
        int t;
        Edge_t(int m, int h, int y) : me(m), p(h), t(y) {} 
        bool operator<(const Edge_t &x) const { return x.t < this->t; }
    };

    while (!que.empty()) {
        Edge_t t = que.top();
        que.pop();
        while (!que.empty() && que.top().t == t.t && que.top().me == t.me)
        ...
    }

  • 可能某Edge h 确实跟pop出来的Edge t是代表的是同一个节点——也就是h.me==t.me ，并且代价相同。但是在堆中，还有同等代价的Edge p，其终点不是t.me ——也就是p.me!=t.me ，然后该Edge p 在堆中的位置处在Edge h 前面，所以上面那个while就没办法获得Edge h 从而无法获取完整的parent list。

  • 另一种情况更为严重——如果某边是0权重，那么就可能出现“把t.me加到result set之后，后面的循环才产生出另一条与src到t.me等代价的路径”——所以当pop出Edge t 后立刻寻找同等代价的路径是不行的，因为该边其实还没有进入到堆里

考虑自循环边

  • 直接判断要求某点A邻接的点不与A相同即可实现

因为有0权重的边，所以可能有0权重环路，所以后面的dfs要注意

  • dfs递归访问某条路径时要维护已经访问到的节点的列表，确保不重复访问该条路径上已经出现过的点，做法是维护一个visit数组，有点类似回溯法

INF的取值要注意

  • dfs过程中有可能访问的那条路径无法从src到dest，从而递归到最深的那次dfs的调用会返回INF，如果INF是0xFFFFFFF，加上后面的权重，就会溢出，从而使得INF+weight[i]不再是INF

自己生成数据对拍时

  • 要注意不要生成多重边，网上很多ac的代码都是不支持多重边的

代码

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f

using namespace std;
struct Node {
    int index;
    vector<int> adj;
};
Node v[600];
int length[600][600]; // length[i][j]记录从node i到node j的length
int TIME[600][600]; // TIME[i][j]记录从node i到node j的用时
vector<int> tp[600];// node's parent list
int tpResult[600];// 最终的node的parent

int BEGIN, END; // 题目输入的天梯队员的起点和要到达的终点
int vertexCnt, edgeCnt;

int dijstra(int weight[][600]);
int DFS(bool isLength);
void outp(int f, int index);

int main(int argc, char** argv) {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                TIME[i][j] = INF;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                length[i][j] = INF;
            }
        }
        for (int i = 0; i < n; i++) {
            v[i].index = i;
            v[i].adj.clear();
        }
        for (int i = 0; i < n; i++) {
            tp[i].clear();
        }

        vertexCnt = n, edgeCnt = m;
        int v1, v2, one, l, t;
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d%d%d", &v1, &v2, &one, &l, &t);
            v[v1].adj.push_back(v2);
            // 这样做是为了避免输入多重边——比如说从i到j有多条边，那么我们直接选最小代价的边即可
            length[v1][v2] = length[v1][v2] < l ? length[v1][v2] : l;
            TIME[v1][v2] = TIME[v1][v2] < t ? TIME[v1][v2] : t;
            if (!one) {
                v[v2].adj.push_back(v1);
                length[v2][v1] = length[v2][v1] < l ? length[v2][v1] : l;
                TIME[v2][v1] = TIME[v2][v1] < t ? TIME[v2][v1] : t;
            }
        }
        scanf("%d%d", &BEGIN, &END);
        if (BEGIN == END) {
            cout << "Time = "
                 << "0"
                 << "; Distance = "
                 << "0"
                 << ": ";
            cout << BEGIN << " => " << END << endl;
            continue;
        }
        if (n == 2) {
            cout << "Time = " << TIME[BEGIN][END] << "; Distance = " << length[BEGIN][END] << ": ";
            cout << BEGIN << " => " << END << endl;
            continue;
        }

        int timeEND = dijstra(TIME);
//        outp(END, 0);
        DFS(false);
        vector<int> r1, r2;
        r1.push_back(END);
        // 以下这种构造路径的方式是建立在起点不同于终点的情况下
        int tmp_tp = tpResult[END];
        r1.push_back(tmp_tp);
        while (tmp_tp != BEGIN) {
            tmp_tp = tpResult[tmp_tp];
            r1.push_back(tmp_tp);
        }
        reverse(r1.begin(), r1.end());

        for (int i = 0; i < n; i++) {
            tp[i].clear();
        }
        int lenEND = dijstra(length);
//        outp(END, 0);
        DFS(true);
        r2.push_back(END);
        tmp_tp = tpResult[END];
        r2.push_back(tmp_tp);
        while (tmp_tp != BEGIN) {
            tmp_tp = tpResult[tmp_tp];
            r2.push_back(tmp_tp);
        }
        reverse(r2.begin(), r2.end());

        bool isSame = false;
        if (r1.size() == r2.size()) {
            isSame = true;
            for (int i = 0; i < r1.size(); i++) {
                isSame = (r1[i] == r2[i]) && isSame;
            }
        }
        if (isSame) {
            cout << "Time = " << timeEND << "; Distance = " << lenEND << ": ";
            for (int i = 0; i < r1.size() - 1; i++) {
                cout << r1[i] << " => ";
            }
            cout << r1[r1.size() - 1] << endl;
        } else {
            cout << "Time = " << timeEND << ": ";
            for (int i = 0; i < r1.size() - 1; i++) {
                cout << r1[i] << " => ";
            }
            cout << r1[r1.size() - 1] << endl;
            cout << "Distance = " << lenEND << ": ";
            for (int i = 0; i < r2.size() - 1; i++) {
                cout << r2[i] << " => ";
            }
            cout << r2[r2.size() - 1] << endl;
        }
    }
}

// 参数me是该edge的终点，p是该edge的起点，t出发的源节点到这条edge的终点的代价
struct Edge_t {
    int me;
    int p;
    int t;
    Edge_t(int m, int h, int y) : me(m), p(h), t(y) {} 
    bool operator<(const Edge_t &x) const { return x.t < this->t; }
};

// bfs+优先队列其实就是dijstra算法
// dijstra维护result set，源节点到这个set里的点的最短路径已经被找到
// 所以result set只会有node被加进去而不会有node被踢出去
// 不同于算法导论描述的dijstra算法——算导里的堆是点的堆，
int dijstra(int weight[][600]) {
    int resWei[600];
    priority_queue<Edge_t> que;
    que.push(Edge_t(BEGIN, 0, 0));// 后面用到了t.t+weight[t.me][adj[i]]，所以这里必须要取0
    int cnt = 0;
    bool visit[vertexCnt];  // 记录某点是否已经加入到dijstra的result set里
    memset(visit, 0, sizeof(visit) * sizeof(bool));
    while (!que.empty()) {
        Edge_t t = que.top();
        que.pop();
        // 因为这是Edge的堆，可能会有一些边pop出来时，其终点已经在result set里
        if (visit[t.me]) {
            assert(resWei[t.me] <= t.t);
            if (resWei[t.me] == t.t) {
                tp[t.me].push_back(t.p);
            }
            continue;
        }
        visit[t.me] = true;
        tp[t.me].push_back(t.p);
        resWei[t.me] = t.t;
        const vector<int> &adj = v[t.me].adj;
        int al = adj.size();
        for (int i = 0; i < al; i++) {
            if (adj[i] == t.me)
                continue;
            que.push(Edge_t(adj[i], t.me, t.t + weight[t.me][adj[i]]));
        }
    }
    return resWei[END];
}

int dp[600];
bool dpVisit[600];
static int __dfs(int f, bool isLength);
int DFS(bool isLength) {
    memset(dp, 0xff, sizeof(dp));
    memset(tpResult, 0, sizeof(tpResult));
    memset(dpVisit, 0, sizeof(dpVisit));
    return __dfs(END, isLength);
}
static int __dfs(int f, bool isLength) {
    if (dp[f] > -1) {
        return dp[f];
    }
    if (f == BEGIN) {
        return 0;
    }
    const vector<int> &t = tp[f];
    int result = INF;
    for (int i = 0; i < t.size(); i++) {
        if(t[i]==f)
            continue;
        if (dpVisit[t[i]])  // 代表该节点在这条路径上已经被访问过
            continue;
        dpVisit[f] = true;
        int p = __dfs(t[i], isLength) + (isLength ? 1 : length[t[i]][f]);
        dpVisit[f] = false;
        if (p < result) {
            tpResult[f] = t[i];
            result = p;
        }
    }
    dp[f] = result;
    return result;
}

int path[600];
bool outpVisit[600];
void outp(int f, int index) {
    outpVisit[f] = true;
    if (f == BEGIN) {
        cout << "outp: ";
        for (int i = 0; i < index; i++) {
            cout << path[i] << " ";
        }
        cout << endl;
        outpVisit[f] = true;
        return;
    }
    path[index] = f;
    const vector<int> &t = tp[f];
    for (int i = 0; i < t.size(); i++) {
        if (outpVisit[t[i]])// means that 前辈们已经访问过了，再访问就成环了
            continue;
        outp(t[i], index + 1);
    }
    outpVisit[f] = false;
    return;
}