HDU-2544-最短路(各种最短路径算法)

迪杰斯特拉算法--O(n^2)

#include"iostream"
#include"cstring"
#include"cstdio"
using namespace std;
const int inf = 0x3f3f3f3f;
typedef long long LL;
int map[105][105];
int ans[105], n, m;
bool flag[105];
void dij() {
    for(int i = 2; i <= n; i++)
    ans[i] = map[1][i];
    ans[1] = 0;
    memset(flag, true, sizeof(flag));
    flag[1] = false;
    for(int i = 2; i < n; i++) {
        int v, mn = inf;
        for(int j = 1; j <= n; j++)
        // 此处建议用 <= 因为map和mx都是初始化为inf，如果用 < 可能一个都找不到导致v是随机值而产生RE。当然也可采用其他方式避免v的随机值；
        if(ans[j] <= mn && flag[j]) {
            mn = ans[j];
            v = j;
        }
        for(int j = 1; j <= n; j++)
        if(ans[v] + map[v][j] < ans[j])
        ans[j] = ans[v] + map[v][j];
        flag[v] = false;
    }
}
int main() {
    int a, b, c;
    while(scanf("%d%d", &n, &m) && (n || m)) {
        memset(map, inf, sizeof(map));
        while(m--) {
            scanf("%d%d%d", &a, &b, &c);
            if(map[a][b] > c)
            map[a][b] = map[b][a] = c;
        }
        dij();
        printf("%d
", ans[n]);
    }
    return 0;
}

View Code

迪杰斯特拉算法堆优化--O(nlgn) 以链式前向星建图

#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> PII;
const int MAXN = 10005;
const int INF = 0x3f3f3f3f;
struct Edge {
    int t, w, n;
} edge[MAXN << 1];
int tot, tail[MAXN], dis[MAXN];
bool use[MAXN];
void add(int u, int v, int w) {
    edge[tot].t = v;
    edge[tot].w = w;
    edge[tot].n = tail[u];
    tail[u] = tot++;
}
void dij() {
    memset(dis, INF, sizeof(dis));
    memset(use, false, sizeof(use));
    // PII的first表示权重，second表示节点。后面部分是为了让优先队列每次取最小值 
    priority_queue<PII, vector<PII>, greater<PII> > que;
    for (int i = tail[1]; i != -1; i = edge[i].n) {
        int t = edge[i].t;
        int w = edge[i].w;
        if (w < dis[t]) {
            dis[t] = w;
            que.push({w, t});
        } 
    }
    use[1] = true;
    while (!que.empty()) {
        int v = que.top().second;
        que.pop();
        if (use[v]) continue;
        use[v] = true;
        for (int i = tail[v]; i != -1; i = edge[i].n) {
            int t = edge[i].t;
            int w = edge[i].w;
            if (dis[v] + w < dis[t]) {
                dis[t] = dis[v] + w;
                que.push({dis[t], t});
            }
        }
    }
}
int main() {
    int n, m, u, v, w;
    while (scanf("%d%d", &n, &m) && (n || m)) {
        tot = 0;
        memset(tail, -1, sizeof(tail));
        while (m--) {
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, w);
            add(v, u, w);
        }
        dij();
        printf("%d
", dis[n]);
    }
    return 0;
}

View Code

迪杰斯特拉算法堆优化--O(nlgn) 以vector建图

#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> PII;
const int MAXN = 105;
const int INF = 0x3f3f3f3f;
vector<PII> vc[MAXN];
int dis[MAXN];
bool use[MAXN];
void dij() {
    memset(dis, INF, sizeof(dis));
    memset(use, false, sizeof(use));
    priority_queue<PII, vector<PII>, greater<PII> > que;
    for (int i = 0; i < vc[1].size(); i++) {
        PII p = vc[1][i];
        if (p.second < dis[p.first]) {
            dis[p.first] = p.second;
            que.push({dis[p.first], p.first});
        }
    }
    use[1] = true;
    while (!que.empty()) {
        int v = que.top().second;
        que.pop();
        if (use[v]) continue;
        use[v] = true;
        for (int i = 0; i < vc[v].size(); i++) {
            PII p = vc[v][i];
            if (dis[v] + p.second < dis[p.first]) {
                dis[p.first] = dis[v] + p.second;
                que.push({dis[p.first], p.first});
            }
        }
    }
}
int main() {
    int n, m, u, v, w;
    while (scanf("%d%d", &n, &m) && (n || m)) {
        for (int i = 1; i <= n; i++) vc[i].clear();
        while (m--) {
            scanf("%d%d%d", &u, &v, &w);
            vc[u].push_back({v, w});
            vc[v].push_back({u, w});
        }
        dij();
        printf("%d
", dis[n]);
    }
    return 0;
}

View Code

弗洛伊德算法--O(n^3)

#include"iostream"
#include"cstring"
#include"cstdio"
using namespace std;
const int inf = 0x3f3f3f3f;
typedef long long LL;
int map[105][105];
int n, m;
void Floyd() {
    for(int k = 1; k <= n; k++)
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
    if(map[i][k] + map[k][j] < map[i][j])
    map[i][j] = map[i][k] + map[k][j];
}
int main() {
    int a, b, c;
    while(scanf("%d%d", &n, &m) && (n || m)) {
        memset(map, inf, sizeof(map));
        while(m--) {
            scanf("%d%d%d", &a, &b, &c);
            if(map[a][b] > c)
            map[a][b] = map[b][a] = c;
        }
        Floyd();
        printf("%d
", map[1][n]);
    }
    return 0;
}

View Code

SPFA算法--O(KE)--E是边数，K一般为2-3

#include"iostream"
#include"cstring"
#include"cstdio"
#include"queue"
using namespace std;
const int inf = 0x3f3f3f3f;
typedef long long LL;
int map[105][105];
int ans[105], n, m;
bool flag[105];
void SPFA() {
    memset(ans, inf, sizeof(ans));
    memset(flag, true, sizeof(flag));
    ans[1] = 0;
    queue<int>q;
    q.push(1); flag[1] = false;
    while(!q.empty()) {
        int v = q.front();
        flag[v] = true;
        q.pop();
        for(int i = 1; i <= n; i++)
        if(ans[v] + map[v][i] < ans[i]) {
            ans[i] = ans[v] + map[v][i];
            if(flag[i]) {
                q.push(i);
                flag[i] = false;
            }
        }
    }
}
int main() {
    int a, b, c;
    while(scanf("%d%d", &n, &m) && (n || m)) {
        memset(map, inf, sizeof(map));
        while(m--) {
            scanf("%d%d%d", &a, &b, &c);
            if(map[a][b] > c)
            map[a][b] = map[b][a] = c;
        }
        SPFA();
        printf("%d
", ans[n]);
    }
    return 0;
}

View Code

深度优先搜索算法

#include"iostream"
#include"cstring"
#include"cstdio"
#include"queue"
using namespace std;
const int inf = 0x3f3f3f3f;
typedef long long LL;
int map[105][105];
int ans, n, m;
bool flag[105];
void DFS(int i, int k) {
    if(i == n) {
        if(k < ans)
        ans = k;
        return;
    }
    for(int j = 1; j <= n; j++)
    if(flag[j] && k + map[i][j] < ans) {
        flag[j] = false;
        DFS(j, k + map[i][j]);
        flag[j] = true;
    }
}
int main() {
    int a, b, c;
    while(scanf("%d%d", &n, &m) && (n || m)) {
        memset(map, inf, sizeof(map));
        while(m--) {
            scanf("%d%d%d", &a, &b, &c);
            if(map[a][b] > c)
            map[a][b] = map[b][a] = c;
        }
        memset(flag, true, sizeof(flag));
        flag[1] = false;
        ans = inf; DFS(1, 0);
        printf("%d
", ans);
    }
    return 0;
}

View Code