最短路

发布于 10 天前  191 次阅读


内容纲要

Mark一下
Dijk堆优化版本

#include <bits/stdc++.h>
#define MAXV 1010
#define INF 0x3f
using namespace std;

struct edge {
    int to, cost;
};
int n;
vector<edge> G[MAXV];  // G的下标存的是起始点
int d[MAXV];
typedef pair<int, int> P;

void dijk(int s) {
    priority_queue<P, vector<P>, greater<P> > que;
    memset(d, INF, sizeof d);
    d[s] = 0;
    que.push(P(0, s));  //把起点推入队列

    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;  //顶点的编号

        if (d[v] < p.first)
            continue;

        for (int i = 0; i < G[v].size(); i++) {
            edge e = G[v][i];

            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

int main() {
    //  freopen("06.in", "r", stdin);
    //  freopen("06.out", "w", stdout);
    int t;
    scanf("%d%d", &n, &t);

    while (t--) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back({ v, w });
        G[v].push_back({ u, w });
    }

    dijk(1);
    long long sum = 0;

    for (int i = 2; i <= n; i++) {
        sum += d[i];
    }

    printf("%lld", sum);
    //  fclose(stdin);
    //  fclose(stdout);
}

Floyd

#include <bits/stdc++.h>
#define MAX_N 1010
using namespace std;

int dis[MAX_N][MAX_N];
int path[MAX_N][MAX_N];

int main() {
    int n, m;
    cin >> n >> m;
    memset(dis, -1, sizeof(dis));
    memset(path, -1, sizeof(path));

    while (m--) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);

        if (dis[u][v] > w || dis[u][v] == -1) {
            dis[u][v] = w;
            dis[v][u] = w;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (dis[j][i] != -1 && dis[i][k] != -1) {
                    int ndis = dis[j][i] + dis[i][k];

                    if (ndis < dis[j][k] || dis[j][k] == -1) {
                        dis[j][k] = ndis;
                        path[j][k] = i;
                    }
                }
            }
        }
    }

    long long sum = 0;

    for (int i = 2; i <= n; i++) {
        sum += dis[1][i];
    }

    printf("%lld", sum);
}

不爱嘉然小姐十年了。十年里,爱过的每个人都像她。