题目传送门

hdu1874：畅通工程续

解题思路

这题因为数据量比较小，可以使用多种最短路算法来解决，是一道经典的模板题，下面附上floyd算法、dijkstra算法、Bellman-Ford 、spfa算法、以及dijkstra + heap优化的代码。

坑点：这题可能一个城市到另一个城市有多条路径，我们记录的时候，要记录最小的那条路径，不能记录最后的那条路径，解其他题目的时候也要注意。以及，注意城市的起始点是从0开始算还是1开始算。

###Floyd算法

该算法极其暴力，时间复杂度为O(n3)O(n^3),但是算法简单，容易理解，核心代码只有4~5行，非常容易理解。

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 <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 205;
int arr[N][N];
int n, m, st, ed;
inline void init()
{
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            arr[i][j] = (i == j ? 0 : INF);
}

void Floyd()
{
    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j) 
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
}

int main()
{
    int a, b, c;
    while(cin >> n >> m) {
        init();
        for(int i = 0; i < m; ++i) {
            cin >> a >> b >> c;
            if(arr[a][b] > c) arr[a][b] = arr[b][a] = c;
        }
        Floyd();
        cin >> st >> ed;
        cout << (arr[st][ed] == INF ? -1 : arr[st][ed]) << endl;
    }
    return 0;
}

Dijsktra算法

这个算法是用来针对无负边权的单源最短路径问题的，它比floyd算法高效。 对这里这个第一个循环i<=n-1的解释： n个点，1到任何一个点的最短路径边数不会超过n-1，因为就算n个点全部连起来，也只有n-1条边。

因为最短路径是一个不包含回路的简单路径，回路分为正权回路(回路权值之和为正)和负权回路(回路权值之和为负)。如果最短路径中包含正权回路，那么去掉这个回路，一定可以得到更短的路径；如果最短路径中包含负权回路，那么肯定没有最短路径，因为每多走一次负权回路就可以得到更短的路径. 因此最短路径肯定是一个不包含回路的最短路径，即最多包含n-1条边。

容易证明，Dijkstra算法每一次循环可以确定一个顶点的最短路径，所以至多循环n-1次即可完成最短路求解。

算法时间复杂度：O(n2)O(n^2)

注：dijsktra算法无法解决负边权问题。

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
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 205;
int arr[N][N];
int dis[N];
bool vis[N];
int n, m, st, ed;
inline void init()
{
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            arr[i][j] = (i == j ? 0 : INF);
}

void Dijkstra()
{
    int k = 0;
    for(int i = 0; i < n - 1; ++i) {
        int minv = INF;
        for(int j = 0; j < n; ++j) 
            if(dis[j] < minv && !vis[j]) minv = dis[j], k = j;
        
        vis[k] = true;
        for(int v = 0; v < n; ++v) {
            if(arr[k][v] < INF) {
                dis[v] = min(dis[v], dis[k] + arr[k][v]);
            }
        }
    }
}

int main()
{
    int a, b, c;
    while(cin >> n >> m) {
        init();
        for(int i = 0; i < m; ++i) {
            cin >> a >> b >> c;
            if(arr[a][b] > c)
                arr[a][b] = arr[b][a] = c; 
        }
        cin >> st >> ed;
        //初始化距离数组
        for(int i = 0; i < n; ++i) dis[i] = arr[st][i];
        //初始化vis数组
        memset(vis, false, sizeof vis);
        vis[st] = true;
        Dijkstra();
        cout << (dis[ed] == INF ? - 1 : dis[ed]) << endl;
    }
    return 0;
}

Dijsktra + heap 优化

使用优先队列，每次找寻最小距离的点，这里有一个技巧，因为greater对pair的比较，是先比较第一个的，所以把dis[i]放在第一位。

这里如果使用邻接表+优先队列来存储，可以将时间复杂度优化至O(m+n)log(n)O(m + n) log(n)，该算法时间复杂度小于O(n2)O(n^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
//邻接矩阵写法
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 205;
typedef pair<int, int> P;
int arr[N][N];
int dis[N];
bool vis[N];
int n, m, st, ed;

inline void init()
{
    memset(dis, INF, sizeof dis);
    memset(vis, false, sizeof vis);
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            arr[i][j] = (i == j ? 0 : INF);
}

void Dijkstra()
{
    dis[st] = 0;
    priority_queue<P, vector<P>, greater<P> > q;
    q.push({0, st});
    while(q.size()) {
        P now = q.top(); q.pop();
        int vi = now.second;
        if(vis[vi]) continue;
        vis[vi] = true;
        for(int i = 0; i < n; ++i) {
            if(!vis[i] && dis[i] > dis[vi] + arr[vi][i]) {
                dis[i] = dis[vi] + arr[vi][i];
                q.push({dis[i], i});
            }
            
        }
    }
}

int main()
{
    int a, b, c;
    while(cin >> n >> m) {
        init();
        for(int i = 0; i < m; ++i) {
            cin >> a >> b >> c;
            arr[a][b] = arr[b][a] = min(arr[a][b], c);
        }
        cin >> st >> ed;
        Dijkstra();
        cout << (dis[ed] == INF ? -1 : dis[ed]) << 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//邻接表写法
#include <bits/stdc++.h>
#define PUSH(x,y,z) G[x].push_back({y,z})  // 宏函数
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1005;
typedef pair<int, int> P;
int n, m, st, ed;
vector<P> G[N];
int dis[N];
bool vis[N];

inline void init()
{
    for(int i = 0; i < N; ++i) G[i].clear();
    memset(dis, INF, sizeof dis);
    memset(vis, false, sizeof vis);
}


void Dijkstra()
{
    dis[st] = 0;
    priority_queue<P, vector<P>, greater<P> > q;
    q.push({0, st});
    while(q.size()) {
        P now = q.top(); q.pop();
        int u = now.second;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i].first;
            int cost = G[u][i].second;
            if(!vis[v] && dis[v] > dis[u] + cost) {
                dis[v] = dis[u] + cost;
                q.push({dis[v], v});
            }
        }
    }
}


int main()
{
    int a, b, c;
    while(cin >> n >> m) {
        init();
        for(int i = 0; i < m; ++i) {
            cin >> a >> b >> c;
            PUSH(a, b, c);
            PUSH(b, a, c);
        }
        cin >> st >> ed;
        Dijkstra();
        cout << (dis[ed] == INF ? -1 : dis[ed]) << endl;
    }
    return 0;
}

Bellman-flod算法

Djikstra算法无法解决负权边问题，但是这个算法可以解决，并且它的核心语句只有四行，堪称完美。 这里同理，循环n-1次，因为n个点最多的边数是n-1条。 因为这个算法可以检测是否存在负权边，如果存在负权边，则无最短路径，若未出现负权边，则得出结果

我们增加一个pro数组来记录上一次的数据，如果更新后数据未变，则说明所有点的最短路径已经求得，提前结束，可提高效率。

负权检测，若再进行一次松弛，数组改变了，则说明这个图一定含负边权。

**注：**一般使用该算法来解决存在负边权的题目。

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
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1005;
int n, m, st, ed;
int pro[N], dis[N], u[N], v[N], w[N];  //u数组为起点，v数组为终点，w数组为边权，每一个组合表示一条边
bool vis[N]; //判断是否访问过该点

void Bellman_Ford()
{

    for(int k = 0; k < n - 1; ++k) {
        for(int i = 0; i < n; ++i) pro[i] = dis[i];
        for(int i = 0; i < m; ++i) {
            dis[v[i]] = min(dis[v[i]], dis[u[i]] + w[i]);
            dis[u[i]] = min(dis[u[i]], dis[v[i]] + w[i]);  //无向图需要反向做一次松弛
        }
        bool check = false;
        //松弛完毕检测dis数组是否有更新，如果没有更新，则可以判断更新完毕，提高效率
        for(int i = 0; i < n; ++i) 
            if(pro[i] != dis[i]) {
                check = true;
                break;
            }
        if(check) continue;
    }
    bool flag = false;
    for(int i = 0; i < m; ++i) 
        if(dis[v[i]] > dis[u[i]] + w[i]) {
            flag = true;
            break;
        }
    if(flag) cout << "该图含有负权回路" << endl;
}

int main()
{
    while(cin >> n >> m) {
        for(int i = 0; i < m; ++i) cin >> u[i] >> v[i] >> w[i];
        memset(dis, INF, sizeof dis);
        cin >> st >> ed;
        dis[st] = 0;
        Bellman_Ford();
        cout << (dis[ed] == INF ? -1 : dis[ed]) << endl;
    }
    return 0;
}

Bellman-flod算法+队列优化（spfa算法）

这个算法利用BFS思路，还能检测负权边，堪称万能算法，时间复杂度还能接受。 下面给出两种写法：邻接表的写法和邻接矩阵的写法。这个算法跟BFS算法不一样的地方就是，BFS一旦出队的点就不在入队了，而spfa算法，出队的点还有可能入队，因为可能起点到该点的估计值再次变小。

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
//邻接矩阵写法
#include <bits/stdc++.h>
#define PUSH(x,y,z) G[x].push_back({y,z})  // 宏函数
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1005;
typedef pair<int, int> P;
int n, m, st, ed;
int dis[N], arr[N][N];
bool vis[N];

void init()
{
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            arr[i][j] = i == j ? 0 : INF;
    memset(dis, INF, sizeof dis);
    memset(vis, false, sizeof vis);
}

void spfa()
{
    queue<int> q;
    vis[st] = true, dis[st] = 0;
    q.push(st);
    while(q.size()) {
        int now = q.front();
        q.pop(); vis[now] = false;
        for(int i = 0; i < n; ++i) {
            if(dis[i] > dis[now] + arr[now][i]) {
                dis[i] = dis[now] + arr[now][i];
                if(!vis[i]) {
                    vis[i] = true;
                    q.push(i);
                }
            }
        }
    }

}

int main()
{
    int a, b, c;
    while(cin >> n >> m) {
        init();
        for(int i = 0; i < m; ++i) {
            cin >> a >> b >> c;
            arr[a][b] = arr[b][a] = min(arr[a][b], c);
        }
        cin >> st >> ed;
        spfa();
        cout << (dis[ed] == INF ? -1 : dis[ed]) << 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//邻接表写法
#include <bits/stdc++.h>
#define PUSH(x,y,z) vec[x].push_back({y,z})  // 宏函数
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1005;
typedef pair<int, int> P;
int n, m, st, ed;
vector<P> vec[N];
int dis[N];  // 起点到终点的距离
bool vis[N]; // 判断是否在队列里面

void init()
{
    for(int i = 0; i < N; ++i) vec[i].clear();
    memset(dis, INF, sizeof dis);
    memset(vis, false, sizeof vis);
}


void Spfa()
{
    queue<int> q;
    q.push(st); dis[st] = 0, vis[st] = true;
    while(q.size()) {
        int now = q.front(); 
        q.pop(); vis[now] = false;
        for(int i = 0; i < vec[now].size(); ++i) {
            int v = vec[now][i].first;
            if(dis[v] > dis[now] + vec[now][i].second) {
                dis[v] = dis[now] + vec[now][i].second;
                if(!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
        
    }
}

int main()
{
    int a, b, c;
    while(cin >> n >> m) {
        init();
        for(int i = 0; i < m; ++i) {
            cin >> a >> b >> c;
            PUSH(a, b, c);
            PUSH(b, a, c);
        }
        cin >> st >> ed;
        Spfa();
        cout << (dis[ed] == INF ? -1 : dis[ed]) << endl;
    }
    return 0;
}