最短路径算法模版(Dijkstra, Bellman Ford, SPFA, floyd)及例题「C++实现」

一. Dijkstra算法 1.1邻接矩阵版

复杂度较高， 适用点数不大的情况。

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

const int maxn = 105, inf = 0x3f3f3f3f;  // maxn根据题目修改
int G[maxn][maxn], dis[maxn], vis[maxn];

// n个顶点的图，从s出发到达其他所有点的最短路径
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    for (int i = 1; i < n; ++i) {   // 进行n-1次
        int u = 0, mind = inf;
        for (int j = 1; j <= n; ++j) 
            if (!vis[j] && dis[j] < mind) mind = dis[j], u = j;
        vis[u] = true;  // 顶点标记为已访问
        for (int v = 1; v <= n; ++v) {  // 更新最短路径
            if (!vis[v] && dis[v] > dis[u] + G[u][v]) dis[v] = dis[u] + G[u][v];
        }
    }
}

1.2 邻接表版

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

const int maxn = 105, inf = 0x3f3f3f3f;
struct edge {
    int v, w;
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn];

// n个顶点的图，从s出发到达其他所有点的最短路径
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(dis));
    dis[s] = 0;
    for (int i = 1; i < n; ++i) {   // 进行n-1次
        int u = 0, mind = inf;
        for (int j = 1; j <= n; ++j) 
            if (!vis[j] && dis[j] < mind) mind = dis[j], u = j;
        vis[u] = true;  // 顶点标记为已访问
        for (auto &ed : e[u]) {  // 更新最短路径
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) dis[v] = dis[u] + w;
        }
    }
}

1.3 邻接表+堆优化

上述两种算法每次寻找最小距离的顶点时需要遍历所有顶点，每次遍历都需要 O ( n ) O(n) O(n)时间。 使用小根堆来存储「到达其他顶点的距离, 顶点编号」，每次取出堆顶元素, 一次 *** 作复杂度 O ( log ⁡ n ) O(\log n) O(logn) ，算法整体复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)

const int maxn = 105, inf = 0x3f3f3f3f;  // 根据实际情况修改!!!
struct edge {
    int v, w;
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // 大根堆:<距离，顶点>

// n个顶点的图，从s出发到达其他所有点的最短路径
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.emplace(0, s);
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (vis[u]) continue;   // 如果已经访问过
        vis[u] = true;
        for (auto &ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.emplace(dis[v], v);
            } 
        }
    }
}

二. Bellman Ford

Bellman-Ford 算法是一种基于松弛（relax） *** 作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。

每次 *** 作遍历所有的边，复杂度 O ( m ) O(m) O(m) 算法最多执行 n − 1 n - 1 n−1 次， 时间复杂度 O ( n m ) O(nm) O(nm)

const int maxn = 105, inf = 0x3f3f3f3f;
struct edge {
    int v, w;
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn];

bool bellmanFord(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    bool flag;
    for (int i = 0; i < n; ++i) {   // 每次遍历枚举所有的边
        flag = false;  // 如果进行边松弛 *** 作，则flag为true 
        for (int u = 1; u <= n; ++u) {
            if (dis[u] == inf) continue;    // 最短路长度为inf的顶点不可能发生松弛 *** 作
            for (auto &ed : e[u]) {
                int v = ed.v, w = ed.w;
                if (dis[v] > dis[u] + w) flag = true, dis[v] = dis[u] + w;
            }
        }
        if (!flag) break;  // 没有可以松弛的边时就停止算法
    }
    return flag;    // 进行第n次迭代后，如果还能进行松弛，则存在负权环
}

三. SPFA

全称 ：Shortest Path Faster Algorithm

bellman ford队列优化后的算法，只有当每个顶点u的d[u]值改变时，从它出发的边的邻接点 v 的d[v]值才有可能改变。

大多数情况下 SPFA 跑得很快，但其最坏情况下的时间复杂度仍然为 O ( m n ) O(mn) O(mn)

const int maxn = 105, inf = 0x3f3f3f3f;  // 根据题目修改maxn!!!
struct edge {
    int v, w;
};
vector<edge> e[maxn];
int dis[maxn], inq[maxn] = {};
queue<int> q;
void spfa(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0; inq[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        for (auto &ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!inq[v]) q.push(v), inq[v] = true;
            }
        }
    }
}f

四. Floyd算法

以上三种算法都是求单源节点短路径，也就是求从一个特定节点出发到达其他各点的最短路径。

Floyd算法是用来解决全源点最短路径 ，即可以得到图中任意两点的最短路径，该算法使用了动态规划的思想。

算法使用三重循环， 时间复杂度 O ( n 3 ) O(n^3) O(n3) ，不适用于顶点过多的情况。

const int maxn = 102, inf = 0x3f3f3f3f;	// 根据实际情况修改maxn
int f[maxn][maxn];

void floyd(int n) {
    for (int k = 1; k <= n; ++k) {	// k为中间节点
        for (int x = 1; x <= n; ++x) {	
            for (int y = 1; y <= n; ++y) {
                f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
            }
        }
    }
}

例题 1. HDU2544 最短路

Dijkstra 邻接矩阵方法

#include 

using namespace std;

const int maxn = 105, inf = 0x3f3f3f3f;
int G[maxn][maxn], dis[maxn], vis[maxn];

// n个顶点的图，从s出发到达其他所有点的最短路径
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    for (int i = 1; i < n; ++i) {   // 进行n-1次
        int u = 0, mind = inf;
        for (int j = 1; j <= n; ++j) 
            if (!vis[j] && dis[j] < mind) mind = dis[j], u = j;
        vis[u] = true;  // 顶点标记为已访问
        for (int v = 1; v <= n; ++v) {  // 更新最短路径
            if (!vis[v] && dis[v] > dis[u] + G[u][v]) dis[v] = dis[u] + G[u][v];
        }
    }
}

int main() {
    int n, m, a, b, c; 
    while (true) {
        cin >> n >> m;
        if (!n && !m) return 0; // 全0结束
        memset(G, 0x3f, sizeof(G));
        while (m--) {
            scanf("%d%d%d", &a, &b, &c);
            G[a][b] = G[b][a] = c;
        }
        dijkstra(n, 1);
        cout << dis[n] << endl;
    } 
    
    return 0;
}

Dijkstra 邻接表、堆优化

#include 

using namespace std;

struct edge {
    int v, w;
};
const int maxn = 105;
vector<edge> e[maxn];
int dis[maxn], vis[maxn]{};
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // 大根堆:<距离，顶点>

// n个顶点的图，从s出发到达其他所有点的最短路径
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.emplace(0, s);
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (vis[u]) continue;   // 如果已经访问过
        vis[u] = true;
        for (auto &ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.emplace(dis[v], v);
            } 
        }
    }
}

int main() {
    int n, m, a, b, c; 
    while (true) {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) e[i].clear();
        if (!n && !m) return 0; // 全0结束
        while (m--) {
            scanf("%d%d%d", &a, &b, &c);
            e[a].push_back({b, c});
            e[b].push_back({a, c});
        }
        dijkstra(n, 1);
        cout << dis[n] << endl;
    } 
    
    return 0;
}

SPFA

#include 

using namespace std;

const int maxn = 105, inf = 0x3f3f3f3f;  // 根据题目修改maxn!!!
struct edge {
    int v, w;
};
vector<edge> e[maxn];
int dis[maxn], inq[maxn] = {};
queue<int> q;
void spfa(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0; inq[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        for (auto &ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!inq[v]) q.push(v), inq[v] = true;
            }
        }
    }
}

int main() {
    int n, m, a, b, c; 
    while (true) {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) e[i].clear();
        if (!n && !m) return 0; // 全0结束
        while (m--) {
            scanf("%d%d%d", &a, &b, &c);
            e[a].push_back({b, c});
            e[b].push_back({a, c});
        }
        spfa(n, 1);
        cout << dis[n] << endl;
    } 
    
    return 0;
}

2.HDU1874 畅通工程续

SPFA

#include 

using namespace std;

const int maxn = 205, inf = 0x3f3f3f3f;  // 根据题目修改maxn!!!
struct edge {
    int v, w;
};
vector<edge> e[maxn];
int dis[maxn], inq[maxn] = {};
queue<int> q;
void spfa(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0; inq[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        for (auto &ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!inq[v]) q.push(v), inq[v] = true;
            }
        }
    }
}

int main() {
    int n, m, a, b, c, s, t; 
    while (cin >> n >> m) {
        for (int i = 0; i < n; ++i) e[i].clear();
        while (m--) {
            scanf("%d%d%d", &a, &b, &c);
            e[a].push_back({b, c});
            e[b].push_back({a, c});
        }
        scanf("%d%d", &s, &t);
        spfa(n, t);
        cout << (dis[s] == inf ? -1 : dis[s]) << endl;
    } 
    return 0;
}

堆优化 Dijkstra

#include 

using namespace std;

const int maxn = 105, inf = 0x3f3f3f3f;  // 根据实际情况修改!!!
struct edge {
    int v, w;
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn]{};
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // 大根堆:<距离，顶点>

// n个顶点的图，从s出发到达其他所有点的最短路径
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.emplace(0, s);
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (vis[u]) continue;   // 如果已经访问过
        vis[u] = true;
        for (auto &ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.emplace(dis[v], v);
            } 
        }
    }
}

int main() {
    int n, m, a, b, c, s, t; 
    while (cin >> n >> m) {
        for (int i = 0; i < n; ++i) e[i].clear();
        while (m--) {
            scanf("%d%d%d", &a, &b, &c);
            e[a].push_back({b, c});
            e[b].push_back({a, c});
        }
        scanf("%d%d", &s, &t);
        dijkstra(n, t);
        cout << (dis[s] == inf ? -1 : dis[s]) << endl;
    } 
    return 0;
}

3.HDU2066 一个人的旅行

Dijkstra 堆优化，建立超级源点(家的位置)。

#include 

using namespace std;

const int maxn = 1005, inf = 0x3f3f3f3f;  // 根据实际情况修改!!!
struct edge {
    int v, w;
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn]{};
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // 大根堆:<距离，顶点>

// n个顶点的图，从s出发到达其他所有点的最短路径
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.emplace(0, s);
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (vis[u]) continue;   // 如果已经访问过
        vis[u] = true;
        for (auto &ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.emplace(dis[v], v);
            } 
        }
    }
}

int main() {
    int t, s, d, a, b, time, tmp;
    while (cin >> t >> s >> d) {
        for (int i = 1; i <= 1001; ++i) e[i].clear();   // 初始化邻接表
        while (t--) {
            scanf("%d%d%d", &a, &b, &time);
            e[a].push_back({b, time});
            e[b].push_back({a, time});
        }
        // 将 1001设置为源点(家对应的点)
        for (int i = 0; i < s; ++i) scanf("%d", &tmp), e[1001].push_back({tmp, 0});
        vector<int> want(d);
        for (int i = 0; i < d; ++i) scanf("%d", &want[i]);
        dijkstra(s + d + 1, 1001);  // 求家到其他所有顶点的最短路径
        int mi = inf;   // 枚举到想去城市的最短路径，选择最小的
        for (int x : want) mi = min(mi, dis[x]);
        cout << mi << endl;
    } 
    return 0;
}

4. HDU1548 A strange lift

bfs层次遍历，每遍历一层，距离加一。

#include 

using namespace std;

int n, a, b, arr[205], vis[205];
void solve() {
    memset(vis, 0, sizeof(vis));  // 标记是否访问
    for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]);
    queue<int> q;
    q.push(a);  vis[a] = true;
    int step = 0;
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            int u = q.front(); q.pop();
            if (u == b) {   // 到达终点
                cout << step << endl;
                return;  
            } 
            if (u - arr[u] >= 1 && !vis[u - arr[u]]) {
                q.push(u - arr[u]);
                vis[u - arr[u]] = true;
            }
            if (u + arr[u] <= n && !vis[u + arr[u]]) {
                q.push(u + arr[u]);
                vis[u + arr[u]] = true;
            }
        }
        ++step;  // 距离+1
    }
    cout << "-1" << endl;   // 未能到达终点
}

int main() {
    while (scanf("%d%d%d", &n, &a, &b) != 1) {  // 输入参数为1个时结束
        solve();
    }
    return 0;
}

5. HDU3790 最短路径问题

Dijkstra堆优化

#include 

using namespace std;
typedef tuple<int, int, int> tii;

const int maxn = 1005, inf = 0x3f3f3f3f;  // 根据实际情况修改!!!
struct edge {
    int v, w1, w2;
};
vector<edge> e[maxn];
int dis[maxn], cost[maxn], vis[maxn];
priority_queue<tii, vector<tii>, greater<tii>> q; // 大根堆:<距离, 花费, 顶点>

// n个顶点的图，从s出发到达其他所有点的最短路径
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(cost, 0x3f, sizeof(cost));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0; cost[s] = 0;
    q.emplace(0, 0, s);
    while (!q.empty()) {
        int u = get<2>(q.top()); q.pop();
        if (vis[u]) continue;   // 如果已经访问过
        vis[u] = true;
        for (auto &ed : e[u]) {
            int v = ed.v, w1 = ed.w1, w2 = ed.w2;
            if (dis[v] > dis[u] + w1) {
                dis[v] = dis[u] + w1;
                cost[v] = cost[u] + w2;
                q.emplace(dis[v], cost[v], v);
            } else if (dis[v] == dis[u] + w1 && cost[v] > cost[u] + w2) {
                cost[v] = cost[u] + w2;
                q.emplace(dis[v], cost[v], v);
            }
        }
    }
}

int main() {
    int n, m, a, b, d, p, s, t;
    while (cin >> n >> m) {
        if (!n && !m) return 0;
        for (int i = 1; i <= n; ++i) e[i].clear();
        while (m--) {
            scanf("%d%d%d%d", &a, &b, &d, &p);
            e[a].push_back({b, d, p});
            e[b].push_back({a, d, p});
        }
        scanf("%d%d", &s, &t);
        dijkstra(n, s);
        printf("%d %d\n", dis[t], cost[t]);
    }
    return 0;
}

SPFA

#include 

using namespace std;

const int maxn = 1005, inf = 0x3f3f3f3f;  // 根据题目修改maxn!!!
struct edge {
    int v, w1, w2;  // w1: 距离、w2: 花费
};
vector<edge> e[maxn];
int dis[maxn], cost[maxn], inq[maxn] = {};
queue<int> q;
void spfa(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(cost, 0x3f, sizeof(cost));
    dis[s] = 0; cost[s] = 0; inq[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;  // 出队
        for (auto &ed : e[u]) {
            int v = ed.v, w1 = ed.w1, w2 = ed.w2;
            if (dis[v] > dis[u] + w1) {  // 通过u中转到达v的距离更少
                dis[v] = dis[u] + w1;
                cost[v] = cost[u] + w2;
                if (!inq[v]) q.push(v), inq[v] = true;
            } else if (dis[v] == dis[u] + w1 && cost[v] > cost[u] + w2) { // 通过u中转到达v的距离相同，但花费更少
                cost[v] = cost[u] + w2;
                if (!inq[v]) q.push(v), inq[v] = true;
            }
        }
    }
}

int main() {
    int n, m, a, b, d, p, s, t;
    while (cin >> n >> m) {
        if (!n && !m) return 0;
        for (int i = 1; i <= n; ++i) e[i].clear();
        while (m--) {
            scanf("%d%d%d%d", &a, &b, &d, &p);
            e[a].push_back({b, d, p});
            e[b].push_back({a, d, p});
        }
        scanf("%d%d", &s, &t);
        spfa(n, s);
        printf("%d %d\n", dis[t], cost[t]);
    }
    return 0;
}

6. HDU2112 HDU Today

1. djikstra朴素版，注意细节比较多
   • 起点和终点不一定出现在所有的边中，而且起点、终点可能相同！
   • 使用 哈希表 unordered_map 来映射地名于编号
   • 两个顶点之间可能有多条边，因为求的是最短路径，最终只保留最短的一条。

#include 

using namespace std;

int id = 0;
unordered_map<string, int> mp;

const int maxn = 105, inf = 0x3f3f3f3f;  // maxn根据题目修改
int G[maxn][maxn], dis[maxn], vis[maxn];

// n个顶点的图，从s出发到达其他所有点的最短路径
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    for (int i = 1; i < n; ++i) {   // 进行n-1次
        int u = 0, mind = inf;
        for (int j = 1; j <= n; ++j) 
            if (!vis[j] && dis[j] < mind) mind = dis[j], u = j;
        vis[u] = true;  // 顶点标记为已访问
        for (int v = 1; v <= n; ++v) {  // 更新最短路径
            if (!vis[v] && dis[v] > dis[u] + G[u][v]) dis[v] = dis[u] + G[u][v];
        }
    }
}

int main() {  
    int n, t;
    char start[35], end[35], s1[35], s2[35];
    while (scanf("%d", &n)) {
        if (n == -1) return 0;  // 终止
        id = 0; mp.clear();
        memset(G, 0x3f, sizeof(G));
        scanf("%s%s", start, end);
        mp[start] = ++id;
        if (!mp.count(end)) mp[end] = ++id;  // start和end可能是一个点，并且都没有出现在公交站中
        while (n--) {
            scanf("%s%s%d", s1, s2, &t);
            if (mp.count(s1) == 0) mp[s1] = ++id;
            if (mp.count(s2) == 0) mp[s2] = ++id;
            if (G[mp[s1]][mp[s2]] > t) G[mp[s1]][mp[s2]] = G[mp[s2]][mp[s1]] = t;  // 可能有重复边
        }
        dijkstra(id, mp[start]);
        cout << (dis[mp[end]] == inf ?  -1 : dis[mp[end]]) << endl;
    }

    return 0;
}

2. Dijkstra堆优化
   • 起点和终点不一定出现在所有的边中，而且起点、终点可能相同！

#include 

using namespace std;

int id = 0;
unordered_map<string, int> mp;

const int maxn = 155, inf = 0x3f3f3f3f;  // 根据实际情况修改!!!
struct edge {
    int v, w;
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn]{};
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // 大根堆:<距离，顶点>

// n个顶点的图，从s出发到达其他所有点的最短路径
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.emplace(0, s);
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (vis[u]) continue;   // 如果已经访问过
        vis[u] = true;
        for (auto &ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.emplace(dis[v], v);
            } 
        }
    }
}
int main() {  
    int n, t;
    char start[35], end[35], s1[35], s2[35];
    while (scanf("%d", &n)) {
        if (n == -1) return 0;  // 终止
        id = 0; mp.clear();
        for (int i = 1; i < maxn; ++i) e[i].clear();
        scanf("%s%s", start, end);
        mp[start] = ++id;
        if (!mp.count(end)) mp[end] = ++id;  // start和end可能是一个点，并且都没有出现在公交站中
        while (n--) {
            scanf("%s%s%d", s1, s2, &t);
            if (mp.count(s1) == 0) mp[s1] = ++id;
            if (mp.count(s2) == 0) mp[s2] = ++id;
            e[mp[s1]].push_back({mp[s2], t});
            e[mp[s2]].push_back({mp[s1], t});
        }
        dijkstra(id, mp[start]);
        cout << (dis[mp[end]] == inf ?  -1 : dis[mp[end]]) << endl;
    }

    return 0;
}

7. HDU2680 Choose the best route

Dijkstra 堆优化

• 边是有向边
• 将n + 1设置为起点，与其相邻的顶点(车站) 距离设置为0

#include 

using namespace std;

const int maxn = 1005, inf = 0x3f3f3f3f;  // 根据实际情况修改!!!
struct edge {
    int v, w;
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn]{};
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // 大根堆:<距离，顶点>

// n个顶点的图，从s出发到达其他所有点的最短路径
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.emplace(0, s);
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (vis[u]) continue;   // 如果已经访问过
        vis[u] = true;
        for (auto &ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.emplace(dis[v], v);
            } 
        }
    }
}

int main() {  
    int n, m, s, p, q, t;
    while (scanf("%d%d%d", &n, &m, &s)) {
        for (int i = 1; i <= n + 1; ++i) e[i].clear();
        while (m--) {
            scanf("%d%d%d", &p, &q, &t);
            e[p].push_back({q, t});
        }
        int w, tmp; cin >> w;
        while (w--) {
            scanf("%d", &tmp);
            e[n + 1].push_back({tmp, 0});
        }
        dijkstra(n + 1, n + 1);
        printf("%d\n", (dis[s] == inf ? -1 : dis[s]));
    }
    return 0;
}

8. HDU1869 六度分离

floyd算法，求任意两点之间的最大距离。

六度分离，即中间最多6个点，则两个点的最大距离为7，若大于7，则不符合“六度分离”理论。

#include 

using namespace std;
const int maxn = 102, inf = 0x3f3f3f3f;
int f[maxn][maxn];

bool floyd(int n) {
    for (int k = 1; k <= n; ++k) {  // k为中间节点
        for (int x = 1; x <= n; ++x) {  
            for (int y = 1; y <= n; ++y) {
                f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (f[i][j] > 7) return false;
        }
    }
    return true;
}

int main() {
    int n, m, x, y;
    while (~scanf("%d%d", &n, &m)) {
        memset(f, 0x3f, sizeof(f));
        for (int i = 1; i <= n; ++i) f[i][i] = 0; // 到自身的距离为0
        while (m--) {
            scanf("%d%d", &x, &y);
            f[x + 1][y + 1] = f[y + 1][x + 1] = 1;
        }
        if (floyd(n)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

9.HDU1596 find the safest road

方法一，floyd算法，稍微修改下松弛 *** 作的代码。

#include 

using namespace std;
const int maxn = 1003;
float f[maxn][maxn];

void floyd(int n) {
    for (int k = 1; k <= n; ++k) {  // k为中间节点
        for (int x = 1; x <= n; ++x) {  
            for (int y = 1; y <= n; ++y) {
                f[x][y] = max(f[x][y], f[x][k] * f[k][y]);
            }
        }
    }
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf("%f", &f[i][j]);
        floyd(n);
        int q, from, to;
        scanf("%d", &q);
        while (q--) {
            scanf("%d%d", &from, &to);
            if (!f[from][to]) printf("What a pity!\n");
            else printf("%.3f\n", f[from][to]);
        }
    }
    return 0;
}

方法二、Dijkstra

#include 

using namespace std;
const int maxn = 1005, inf = 0x3f3f3f3f;  // maxn根据题目修改
float G[maxn][maxn], dis[maxn];
bool vis[maxn];

// n个顶点的图，从s出发到达其他所有点的最短路径
void dijkstra(int n, int s, int to) {
    memset(dis, 0, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 1;
    for (int i = 1; i < n; ++i) {   // 进行n-1次
        int u = 0;
        float maxd = 0;
        for (int j = 1; j <= n; ++j) 
            if (!vis[j] && dis[j] > maxd) maxd = dis[j], u = j;
        vis[u] = true;  // 顶点标记为已访问
        for (int v = 1; v <= n; ++v) {  // 更新最短路径
            if (!vis[v] && dis[v] < dis[u] * G[u][v]) dis[v] = dis[u] * G[u][v];
        }
    }
    if (!dis[to]) printf("What a pity!\n");
    else printf("%.3f\n", dis[to]);
}
int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf("%f", &G[i][j]);
        int q, from, to;
        scanf("%d", &q);
        while (q--) {
            scanf("%d%d", &from, &to);
            dijkstra(n, from, to);
        }
    }
    return 0;
}

参考文章及书籍

1. 胡凡、曾磊 《算法笔记》
2. https://oi-wiki.org/graph/
3. https://acm.hdu.edu.cn/