<= 点个赞吧QWQ

爱(抄)学(题)习(解)党必看!!!

$\Large\color{gold}{题目传送门}$

<= 强烈推荐收藏!!!

这是一道非常简单的单源最短路裸题，

由于数据很小，所以我们可以用4种方法来求，分别是：

1.dijkstra朴素版：$O(n ^ 2)$

Code

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int g[N][N];
int dist[N];
bool vis[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    for (int i = 1; i < n; ++ i )
    {
        int t = -1;
        for (int j = 1; j <= n; ++ j )
            if (!vis[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // if (t == n) break;

        for (int j = 1; j <= n; ++ j )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        vis[t] = true;
    }

    int res = -1;
    for (int i = 1; i <= n; ++ i )
    {
        if (dist[i] == 0x3f3f3f3f) return -1;
        res = max(res, dist[i]);
    }
    return res;
}

int main()
{
    memset(g, 0x3f, sizeof g);

    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a = 0, b = 0, c = 0;
        scanf("%d%d%d", &a, &b, &c);
        if (a == b) continue;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    printf("%d\n", dijkstra());
    return 0;
}

2.dijkstra优化版：$O(m \times log2(n))$

Code

#include <queue>
#include <cstring>
#include <iostream>

using namespace std;

typedef pair <int, int> PII;

const int N = 150010;

int n, m;
int h[N], e[N], w[N], ne[N], idx;
bool vis[N];
int dist[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue <PII, vector <PII>, greater <PII> > heap;
    heap.emplace(0, 1);

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second;

        if (vis[ver]) continue;
        vis[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.emplace(dist[j], j);
            }
        }
    }

    int res = -1;
    for (int i = 2; i <= n; ++ i )
        res = max(res, dist[i]);
    if (res == 0x3f3f3f3f) res = -1;
    return res;
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a = 0, b = 0, c = 0;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    printf("%d\n", dijkstra());
    return 0;
}

3.spfa: $O(m) 至 O(nm)$

Code

#include <queue>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
bool vis[N];
int dist[N];
int h[N], e[N], ne[N], w[N], idx;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue <int> q;
    vis[1] = true;
    q.push(1);

    while (q.size())
    {
        int t = q.front();
        q.pop();

        vis[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!vis[j])
                {
                    q.push(j);
                    vis[j] = true;
                }
            }
        }
    }

    int res = 0;
    for (int i = 2; i <= n; ++ i )
        res = max(res, dist[i]);
    if (res == 0x3f3f3f3f) res = -1;
    return res;
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++ i )
    {
        int a = 0, b = 0, w = 0;
        scanf("%d%d%d", &a, &b, &w);
        add(a, b, w), add(b, a, w);
    }

    int res = spfa();
    printf("%d\n", res);
    return 0;
}

4.floyd: $O(n ^ 3)$

Code

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int g[N][N];

void floyd()
{
    for (int k = 1; k <= n; ++ k )
        for (int i = 1; i <= n; ++ i )
            for (int j = 1; j <= n; ++ j )
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

int main()
{
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; ++ i )
        g[i][i] = 0;

    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a = 0, b = 0, c = 0;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    floyd();

    int res = -1;
    for (int i = 2; i <= n; ++ i ) // 注意这里必须从2开始
        res = max(g[1][i], res);

    printf("%d\n", res == 0x3f3f3f3f ? -1 : res);
    return 0;
}

⬇ 欢迎评论!!!