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

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

#include"iostream"

#include"cstring"

#include"cstdio"

using namespace std;

const int inf = 0x3f3f3f3f;

typedef long long LL;

int map[][];

int ans[], n, m;

bool flag[];

void dij() {

    for(int i = ; i <= n; i++)

    ans[i] = map[][i];

    ans[] = ;

    memset(flag, true, sizeof(flag));

    flag[] = false;

    for(int i = ; i < n; i++) {

        int v, mn = inf;

        for(int j = ; j <= n; j++)

        // 此处建议用 <= 因为map和mx都是初始化为inf，如果用 < 可能一个都找不到导致v是随机值而产生RE。当然也可采用其他方式避免v的随机值；

        if(ans[j] <= mn && flag[j]) {

            mn = ans[j];

            v = j;

        }

        for(int j = ; 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\n", ans[n]);

    }

    return ;

}

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

#include "bits/stdc++.h"

using namespace std;

typedef pair<int, int> PII;

const int MAXN = ;

const int INF = 0x3f3f3f3f;

struct Edge {

    int t, w, n;

} edge[MAXN << ];

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[]; i != -; 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[] = true;

    while (!que.empty()) {

        int v = que.top().second;

        que.pop();

        if (use[v]) continue;

        use[v] = true;

        for (int i = tail[v]; i != -; 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 = ;

        memset(tail, -, sizeof(tail));

        while (m--) {

            scanf("%d%d%d", &u, &v, &w);

            add(u, v, w);

            add(v, u, w);

        }

        dij();

        printf("%d\n", dis[n]);

    }

    return ;

}

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

#include "bits/stdc++.h"

using namespace std;

typedef pair<int, int> PII;

const int MAXN = ;

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 = ; i < vc[].size(); i++) {

        PII p = vc[][i];

        if (p.second < dis[p.first]) {

            dis[p.first] = p.second;

            que.push({dis[p.first], p.first});

        }

    }

    use[] = true;

    while (!que.empty()) {

        int v = que.top().second;

        que.pop();

        if (use[v]) continue;

        use[v] = true;

        for (int i = ; 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 = ; 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\n", dis[n]);

    }

    return ;

}

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

#include"iostream"

#include"cstring"

#include"cstdio"

using namespace std;

const int inf = 0x3f3f3f3f;

typedef long long LL;

int map[][];

int n, m;

void Floyd() {

    for(int k = ; k <= n; k++)

    for(int i = ; i <= n; i++)

    for(int j = ; 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\n", map[][n]);

    }

    return ;

}

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[][];

int ans[], n, m;

bool flag[];

void SPFA() {

    memset(ans, inf, sizeof(ans));

    memset(flag, true, sizeof(flag));

    ans[] = ;

    queue<int>q;

    q.push(); flag[] = false;

    while(!q.empty()) {

        int v = q.front();

        flag[v] = true;

        q.pop();

        for(int i = ; 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\n", ans[n]);

    }

    return ;

}

深度优先搜索算法

#include"iostream"

#include"cstring"

#include"cstdio"

#include"queue"

using namespace std;

const int inf = 0x3f3f3f3f;

typedef long long LL;

int map[][];

int ans, n, m;

bool flag[];

void DFS(int i, int k) {

    if(i == n) {

        if(k < ans)

        ans = k;

        return;

    }

    for(int j = ; 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[] = false;

        ans = inf; DFS(, );

        printf("%d\n", ans);

    }

    return ;

}

巴特西

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

最新文章

热门文章