图论总结

深搜和广搜

岛屿数量(深搜版)

通过深搜，每遇到一个没遍历过的陆地，计数器就增加1。遍历时需要visited数组判断是否遍历过。对于MN的二维表格，利用DFS进行搜索，时间复杂度为 $O(m*n)$。

对于n个节点，e条边，DFS的时间复杂度为$O(n+e)$

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
//深搜模板题
#include<iostream>
#include<vector>

using namespace std;

int dire[4][2] = {1,0,-1,0,0,1,0,-1}; //四个方向
int count = 0;

void dfs(int x,int y,vector<vector<int>>& grid,vector<vector<int>>& visited){ //从一个确定的岛屿块出发，把这个岛遍历完
    if(grid[x][y]==0||visited[x][y]) return;  //水和遍历的地方返回
    visited[x][y] = 1; //不是水且未遍历过的地块，标记并且进行后续操作
    for(int i=0;i<4;i++){
        int next_x = x+dire[i][0];
        int next_y = y+dire[i][1];
        if(next_x<0||next_x>=grid.size()||next_y<0||next_y>=grid[0].size()) continue;
        dfs(next_x,next_y,grid,visited);
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid(n,vector<int>(m,0));
    vector<vector<int>> visited(n,vector<int>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j]==1&&visited[i][j]==0){
                count++;
                dfs(i,j,grid,visited);
            }
        }
    }
    cout<<count<<endl;
}

岛屿数量(广搜版)

需要用到队列，每一个节点，只要加入队列，就进行标记。对于MN的二维表格，利用BFS进行搜索，时间复杂度为 $O(m*n)$。

对于n个节点，e条边，BFS的时间复杂度为$O(n+e)$

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
//广搜模板题
#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int dire[4][2] = {1,0,-1,0,0,1,0,-1}; //四个方向
void bfs(int x,int y,vector<vector<int>>& visited,vector<vector<int>>& grid){
    queue<int> que;
    que.push(x);
    que.push(y);
    visited[x][y] = 1;
    while(!que.empty()){
        int cur_x = que.front(); que.pop();
        int cur_y = que.front(); que.pop();
        for(int i=0;i<4;i++){
            int next_x = cur_x + dire[i][0];
            int next_y = cur_y + dire[i][1];
            if(next_x<0||next_x>=grid.size()||next_y<0||next_y>=grid[0].size()) continue;
            if(visited[next_x][next_y]==0&&grid[next_x][next_y]==1){
                que.push(next_x);
                que.push(next_y);
                visited[next_x][next_y] = 1;
            }
        }
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    int result = 0;
    vector<vector<int>> grid(n,vector<int>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    vector<vector<int>> visited(n,vector<int>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(visited[i][j]==0&&grid[i][j]==1){
                result++;
                bfs(i,j,visited,grid);
            }
        }
    }
    cout<<result<<endl;
}

并查集

并查集用于判断两个元素是否在一个集合当中，可以做到将两个元素添加到一个集合中以及判断两个元素在不在一个集合,时间复杂度在 $O(logn)$ 和 $O(1)$ 之间，随着查询合并操作增加，越来越趋近于 $O(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
int n = 1005;
vector<int> father = vector<int>(n,0);

//并查集初始化
void init(){
    for(int i=0;i<n;i++){
        father[i] = i;
    }
}

//寻根
int find(int u){
    if(u==father[u]) return u; //当发现一个节点指向自己，则为根节点，就可以返回
    father[u] = find(father[u]); //路径压缩
    return father[u];
}

void join(int u,int v){
    u = find(u);
    v = find(v);
    if(u==v) return;
    father[v] = u;
}

bool issame(int u,int v){
    u = find(u);
    v = find(v);
    return u==v;
}

岛屿问题(并查集)

用并查集也可以完成岛屿问题，代码如下：

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
#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;

int a=5000;
vector<int> father(a,0);
int dire[4][2] = {1,0,-1,0,0,1,0,-1};

void init(){
    for(int i=0;i<a;i++){
        father[i] = i;
    }
}

int find(int u){
    if(u==father[u]) return u;
    else return father[u] = find(father[u]);
}

void join(int u,int v){
    u = find(u);
    v = find(v);
    if(u==v) return;
    father[u] = v;
}

bool issame(int u,int v){
    u = find(u);
    v = find(v);
    return u==v;
}

int main(){
    int n,m;
    cin>>n>>m;
    init();
    vector<vector<int>> grid(n,vector<int>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j]==1){
                int id1 = i*m+j; //用一个数字唯一标记某个节点
                for(int k=0;k<4;k++){
                    int ni = i+dire[k][0];
                    int nj = j+dire[k][1];
                    if(ni>=0 && ni<n && nj>=0 && nj<m && grid[ni][nj]==1){
                        int id2 = ni*m + nj;
                        join(id1,id2);
                    }
                }

            }
        }
    }
    unordered_set<int> roots;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j]==1){
                roots.insert(find(i*m+j));
            }
        }
    }
    cout<<roots.size()<<endl;
}

拓扑排序

把有向无环图进行线性排序的算法都可以叫做拓扑排序，实现拓扑排序算法有卡恩算法(BFS)和DFS.
实现核心步骤为:1.找到入度为0的节点，加入结果集 2.将该节点从图中移除

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
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int main() {
    int m, n, s, t;
    cin >> n >> m;
    vector<int> inDegree(n, 0); // 记录每个文件的入度

    unordered_map<int, vector<int>> umap;// 记录文件依赖关系，用邻接表也可以vector<list<int>>
    vector<int> result; // 记录结果

    while (m--) {
        // s->t，先有s才能有t
        cin >> s >> t;
        inDegree[t]++; // t的入度加一
        umap[s].push_back(t); // 记录s指向哪些文件
    }
    queue<int> que;
    for (int i = 0; i < n; i++) {
        // 入度为0的文件，可以作为开头，先加入队列
        if (inDegree[i] == 0) que.push(i);
        //cout << inDegree[i] << endl;
    }
    // int count = 0;
    while (que.size()) {
        int  cur = que.front(); // 当前选中的文件
        que.pop();
        //count++;
        result.push_back(cur);
        vector<int> files = umap[cur]; //获取该文件指向的文件
        if (files.size()) { // cur有后续文件
            for (int i = 0; i < files.size(); i++) {
                inDegree[files[i]] --; // cur的指向的文件入度-1
                if(inDegree[files[i]] == 0) que.push(files[i]);
            }
        }
    }
    if (result.size() == n) {
        for (int i = 0; i < n - 1; i++) cout << result[i] << " ";
        cout << result[n - 1];
    } else cout << -1 << endl;
}

最小生成树

最小生成树是连通所有节点的最小子图，即以最小的成本（边的权值）将图中所有节点链接到一起。

prim算法(适合稠密图)

prim算法是维护节点的集合，时间复杂度 $O(n^2)$,其中n为节点数量。

prim算法三部曲为：

  1. 选距离生成树最近的节点
  2. 最近节点加入生成树
  3. 更新非生成树节点到生成树的距离(即更新minDist数组)
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
#include<iostream>
#include<vector>
#include<climits>
#include<list>

using namespace std;

struct edge{
    int to,val;
    edge(int t,int v): to(t),val(v) {}
};

int main(){
    int n,m;
    cin>>n>>m;
    vector<int> mindis(n+1,INT_MAX);
    vector<int> intree(n+1,0); //判断是否在生成树内
    vector<list<edge>> grid(n+1);
    //初始化
    mindis[1] = 0;
    while(m--){
        int s,t,val;
        cin>>s>>t>>val;
        grid[s].push_back(edge(t,val)); //双向图
        grid[t].push_back(edge(s, val));  
    }
    for(int i=1;i<n;i++){
        int minval = INT_MAX;
        int cur = -1;
        for(int j=1;j<=n;j++){
            if(intree[j]==0&&mindis[j]<minval){
                minval = mindis[j];
                cur = j;
            }
        }
        intree[cur] = 1; //将最近的节点添加
        for(edge e:grid[cur]){
            if(intree[e.to]==0&&e.val<mindis[e.to]){ //更新距离
                mindis[e.to] = e.val;
            }
        }
    }
    int result = 0;
    for(int i=1;i<=n;i++){
        result+=mindis[i]; 
    }
    cout<<result<<endl;
}

kruskal算法(适合稀疏图并查集)

kruskal算法是维护边的集合,时间复杂度 $O(eloge)$，其中e为边的数量。

主要思路为:

  1. 边的权值排序(最小堆，快排都行，复杂度为eloge)，因为要优先选最小的边到生成树里
  2. 遍历排序后的边，如果边首尾的两个节点在一个集合，则连接该边会出现环。若不在一个集合，加入到最小生成树，并把两个节点加入到一个集合。
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

#include<iostream>
#include<vector>
#include<climits>
#include<list>
#include<queue>
using namespace std;


struct edge{
    int s,t,val;
    bool operator<(const edge& other)const{
        return val>other.val;
    }
};
int a = 10005;
vector<int> father(a,0);

void init(){
    for(int i=0;i<a;i++){
        father[i] = i;
    }
}

int find(int u){
    if(u==father[u]) return u;
    return father[u] = find(father[u]);
}

void join(int u,int v){
    u = find(u);
    v = find(v);
    if(u==v) return;
    father[u] = v;
}

bool issame(int u,int v){
    return find(u)==find(v);
}

int main(){
    init();
    int n,m;
    cin>>n>>m;
    priority_queue<edge> que;
    while(m--){
        edge e;
        cin>>e.s>>e.t>>e.val;
        que.push(e);
    }
    int result=0;
    while(!que.empty()){
        edge cur = que.top(); que.pop();
        if(!issame(cur.s,cur.t)){
            result+=cur.val;
            join(cur.s,cur.t);
        }
    }
    cout<<result<<endl;
}

最短路问题

dijkstra朴素版(适用于稠密图，边权正)

给出一个有向有权(正)图，输入起点和终点，问最短路径。时间复杂度为 $O(N^2)$ ,它的实现方法为：

  1. 选取离源点最近且visited[cur] ==0的节点
  2. 标记该点visited[cur] == 1
  3. 更新所有未访问节点到源点距离
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
#include<iostream>
#include<vector>
#include<climits>

using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> graph(n+1,vector<int>(n+1,INT_MAX)); //用邻接矩阵保存
    while(m--){
        int s,t,val;
        cin>>s>>t>>val;
        graph[s][t] = val;
    }
    vector<int> mindis(n+1,INT_MAX); //节点到源点的最短路径，初始化为最大值
    vector<int> visited(n+1,0); //标记是否访问过
    mindis[1] = 0; //初始化起始点
    for(int i=1;i<=n;i++){
        int minval = INT_MAX;
        int cur;  //去数组中寻找未访问且最近的节点
        for(int v=1;v<=n;v++){
            if(!visited[v]&&mindis[v]<minval){
                minval = mindis[v];
                cur = v;
            }
        }
        visited[cur] = 1; //标记该点为访问过
        for(int v=1;v<=n;v++){
            if(!visited[v]&&graph[cur][v]!=INT_MAX&&graph[cur][v]+mindis[cur]<mindis[v]){
                mindis[v] = graph[cur][v]+mindis[cur];
            }
        }
    }
    if(mindis[n]!=INT_MAX) cout<<mindis[n]<<endl;
    else cout<<-1<<endl; //不能到达
    return 0;
}

dijkstra堆优化版(邻接表，最小堆，适用于稀疏图，边权正)

时间复杂度为 $O(ElogN)$,e为边的数量，n为节点数量。优化的内容为：

  1. 改为用邻接表来存储
  2. 用最小堆来实现，直接选取mindis最小的节点
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
#include<iostream>
#include<queue>
#include<climits>
#include<list>

using namespace std;

struct edges{
    int to,val; // 目标节点和权值
    edges(int t,int v): to(t),val(v) {} //构造函数
};

struct mycomp{
    bool operator()(const pair<int,int>& lhs,const pair<int,int>& rhs){ // 用于最小堆
        return lhs.second>rhs.second;
    }
};

int main(){
    int n,m;
    cin>>n>>m;
    vector<list<edges>> graph(n+1);//用邻接表存储，n个节点，将边push_back()
    while(m--){
        int s,t,val;
        cin>>s>>t>>val;
        graph[s].push_back(edges(t,val));
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,mycomp> que; // 队列中存放节点pair<int,int>其中第一个int表示节点，第二个表示这个节点的mindis
    vector<int> visited(n+1,0);
    vector<int> mindis(n+1,INT_MAX);
    que.push({1,0});
    while(!que.empty()){
        pair<int,int> cur = que.top(); que.pop(); //直接选取最近的为访问的节点
        visited[cur.first] = 1; // 标记
        for(edges edge:graph[cur.first]){
            if(visited[edge.to]==0&&mindis[edge.to]>cur.second+edge.val){
                mindis[edge.to] = cur.second+edge.val;
                que.push({edge.to,mindis[edge.to]});
            }
        }
    }
    if(mindis[n]!=INT_MAX) cout<<mindis[n]<<endl;
    else cout<<-1<<endl;
    return 0;
}

Bellman_ford(边权正负)

不存在负权回路时

通过对所有的边进行松弛操作n-1次(n为节点数量),即可求得目标最短。松弛的过程根据输入的边而变化，通过松弛n-1次后能确保结果正确。时间复杂度为 $O(NE)$.

其中松弛的操作为:

1
if(mindis[B]>mindis[A]+value) mindis[B] = mindis[A]+value; //即如果从A能够近到达B，那就更新

对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。

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
#include<iostream>
#include<vector>
#include<climits>

using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid; //把每一条边存入即可
    while(m--){
        int s,t,val;
        cin>>s>>t>>val;
        grid.push_back({s,t,val});
    }
    vector<int> mindis(n+1,INT_MAX);
    mindis[1] = 0;
    for(int i=1;i<n;i++){  //松弛n-1次,O(N)
        for(vector<int> &edge:grid){ //O(E)
            int from = edge[0];
            int to = edge[1];
            int value = edge[2];
            if(mindis[from]!= INT_MAX&&mindis[to]>mindis[from] + value){ //mindis[from]!= INT_MAX防止从为计算过的节点出发
                mindis[to] = mindis[from] + value;
            }
        }
    }
    if(mindis[n]!=INT_MAX) cout<<mindis[n]<<endl;
    else cout<<"unconnected"<<endl;
    return 0;
}

SPFA(队列优化算法，实用于稀疏图，越稠密越接近于bellman_ford)

传统的方法下，是对所有边进行松弛，但是没计算过的节点是松弛不了的。

因此可以通过队列来记录上一次松弛更新过的节点。在这种方法下，如果为双向图且所有节点都互相连接，则时间复杂度则会接近 $O(NE)$,一般来说其时间复杂度为 $O(KN)$,如果图为线性单向图，则为 $O(N)$.

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
#include<iostream>
#include<vector>
#include<climits>
#include<list>
#include<queue>

using namespace std;

struct edges{
    int to,val;
    edges(int t,int v): to(t),val(v) {}
};

int main(){
    int n,m;
    cin>>n>>m;
    vector<list<edges>> grid(n+1); //邻接表记录每一个节点连接的边，方便取出节点存入队列
    vector<int> inqueue(n+1,0); //在队列中的元素不添加
    while(m--){
        int s,t,val;
        cin>>s>>t>>val;
        grid[s].push_back(edges(t,val));
    }
    vector<int> mindis(n+1,INT_MAX);

    queue<int> que; //存放节点
    que.push(1); //初始化
    inqueue[1] = 1;
    mindis[1] = 0;

    while(!que.empty()){
        int cur = que.front();
        que.pop();
        inqueue[cur] = 0;
        for(edges edge:grid[cur]){
            if(mindis[edge.to]>mindis[cur]+edge.val){
                mindis[edge.to] = mindis[cur]+edge.val;
                if(inqueue[edge.to]==0){
                    que.push(edge.to);
                    inqueue[edge.to] = 1;
                }
            }
        }
    }
    if(mindis[n]!=INT_MAX) cout<<mindis[n]<<endl;
    else cout<<"unconnected"<<endl;
    return 0;
}

判断负权回路

只需要多松弛一次，如果结果有变化，则代表有负权回路。

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
#include<iostream>
#include<vector>
#include<climits>

using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid; //把每一条边存入即可
    while(m--){
        int s,t,val;
        cin>>s>>t>>val;
        grid.push_back({s,t,val});
    }
    vector<int> mindis(n+1,INT_MAX);
    mindis[1] = 0;
    bool flag = false;
    for(int i=1;i<=n;i++){  //松弛n-1次,O(N)
        for(vector<int> &edge:grid){ //O(E)
            int from = edge[0];
            int to = edge[1];
            int value = edge[2];
            if(i!=n){
                if(mindis[from]!= INT_MAX&&mindis[to]>mindis[from] + value){ //mindis[from]!= INT_MAX防止从为计算过的节点出发
                    mindis[to] = mindis[from] + value;
                }
            }
            else{ //多判断一次
                if(mindis[from]!= INT_MAX&&mindis[to]>mindis[from] + value) flag=true;
            }
        }
    }

    if(flag) cout<<"circle"<<endl;
    else if (mindis[n]!=INT_MAX) cout<<mindis[n]<<endl;
    else cout<<"unconnected"<<endl;
    return 0;
}

单源有限最短路(Dijkstra是贪心，不一定找得到有限最短路)

相比于前面的部分，这里多了一个条件：路径中最多可以经过k 个节点。为了计算这种情况下的最短路径，需要对松弛的次数进行修改。因此本题时间复杂度为 $O(K*E)$.

由于对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离，因此我们这里可以进行k+1次松弛。

当节点为n个，最多n-1条边相连，松弛n-1次。所以当经过小于等于k个节点，最多k+2个节点，因此需要松弛k+1次。

另外，为了确保每次松弛时只计算一次边，相比于使用一个全局的 mindis 数组，必须使用一个额外的数组来保存上一次松弛的结果。这样做可以避免在一次松弛中通过已更新的节点计算不止一条边，从而确保计算的准确性。

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
#include<iostream>
#include<vector>
#include<climits>

using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid; //把每一条边存入即可
    while(m--){
        int s,t,val;
        cin>>s>>t>>val;
        grid.push_back({s,t,val});
    }
    int src,dst,k;
    cin>>src>>dst>>k;

    vector<int> mindis(n+1,INT_MAX);
    mindis[src] = 0;
    vector<int> copy_mindis(n+1);  //用于保存上一次遍历的结果
    for(int i=1;i<=k+1;i++){  //松弛k+1次 O(K)
        copy_mindis = mindis;
        for(vector<int> &edge:grid){ //O(E)
            int from = edge[0];
            int to = edge[1];
            int value = edge[2];
            if(copy_mindis[from]!= INT_MAX&&mindis[to]>copy_mindis[from] + value){ //mindis[from]!= INT_MAX防止从为计算过的节点出发
                mindis[to] = copy_mindis[from] + value;
            }
        }
    }
    if(mindis[dst]!=INT_MAX) cout<<mindis[dst]<<endl;
    else cout<<"unreachable"<<endl;
    return 0;
}

Floyd算法(无向图，多源，边权正负)

时间复杂度为 $O(n^3)$,适用于稠密图且源点较多的情况，如果源点少则可以多次使用dijsktra

思想为动态规划，可以定义一个结构：
$$
grid[i][j][k] = m
$$
表示节点i到节点j，以[1..k]集合中的一个节点为中间节点的最短距离为m。

递推公式可以分为两种情况：

  1. 节点i到j的最短路经过节点k
  2. 节点i到j的最短路不经过节点k
    当经过时：
    $$
    grid[i][j][k] = grid[i][k][k-1] + grid[k][j][k-1];
    $$
    不经过时:
    $$
    grid[i][j][k] = grid[i][j][k-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
#include<iostream>
#include<vector>
#include<climits>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<vector<int>>> grid(n+1,vector<vector<int>>(n+1,vector<int>(n+1,10001))); //初始化为10001大于边权最大值，用INT_MAX会溢出
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        grid[u][v][0] = w;
        grid[v][u][0] = w;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                grid[i][j][k] = min(grid[i][k][k-1] + grid[k][j][k-1],grid[i][j][k-1]);
            }
        }
    }
    int q;
    cin>>q;
    while(q--){
        int start,end;
        cin>>start>>end;
        if(grid[start][end][n]==10001) cout<<-1<<endl;
        else cout<<grid[start][end][n]<<endl;
    }
}

如果用二维数组也可以，更加简单

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
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, 10001));  // 因为边的最大距离是10^4

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
        grid[p2][p1] = val; // 注意这里是双向图

    }
    // 开始 floyd
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
            }
        }
    }
    // 输出结果
    int z, start, end;
    cin >> z;
    while (z--) {
        cin >> start >> end;
        if (grid[start][end] == 10001) cout << -1 << endl;
        else cout << grid[start][end] << endl;
    }
}

A*算法

类似于广搜的优化版本，对于题目127.骑士的攻击，通过判断每一个节点的权值F来将其放入最小堆中，保证每一次取出的节点更加靠近最终结果。

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
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

int moves[1001][1001];
int dire[8][2] = {2,1,-2,-1,2,-1,-2,1,1,2,1,-2,-1,2,-1,-2};
int b1,b2;

struct knight{
    int x,y;
    int g,h,f;
    bool operator< (const knight& k) const{  //利用f的大小来入队列
        return f>k.f;
    }
};

priority_queue<knight> que;

int dis(const knight& k){ //计算到终点欧拉距离
    return (b1-k.x)*(b1-k.x) + (b2-k.y)*(b2-k.y);
}


void astar(const knight& k){
    que.push(k);
    while(!que.empty()){
        knight node = que.top();
        que.pop();
        if(node.x==b1&&node.y==b2) break; //搜到后退出
        for(int i=0;i<8;i++){
            knight next;
            next.x = node.x+dire[i][0];
            next.y = node.y+dire[i][1];
            if(next.x<1||next.x>1000||next.y<1||next.y>1000) continue;
            if(moves[next.x][next.y]==0){ 
                moves[next.x][next.y] = moves[node.x][node.y] +1; //步数加1
                next.g = node.g + 5;
                next.h = dis(next);
                next.f = next.g + next.h;
                que.push(next);
            }
        }
    }

}
int main(){
    int n;
    cin>>n;
    while(n--){
        int a1,a2;
        memset(moves,0,sizeof(moves)); //重置棋盘
        knight start;
        cin>>a1>>a2>>b1>>b2;
        start.x = a1;
        start.y = a2;
        start.g = 0;
        start.h = dis(start);
        start.f = start.h+start.g;
        astar(start);
        while(!que.empty()) que.pop(); //清空队列中的节点
        cout<<moves[b1][b2]<<endl;
    }
    return 0;
}

封面

封面