2 条题解

  • 1
    @ 2023-1-17 11:23:19

    单源最短路径-标准版

    Dijkstra-优先队列优化-O(mlog⁡m)O(m\log m)

    #include <bits/stdc++.h>
using namespace std;
const int MAXN = 100'000;
const int MAXM = 200'000;
int n, m, s; // 点数、边数、出发点编号
struct Edge
{
    int v, w;
};
vector<Edge> e[MAXN + 5];
int dis[MAXN + 5];  // dis[i]: s->i 的最短路
bool vis[MAXN + 5]; // vis[i]: i 号点是否已经确定了

struct Point
{
    int id, dis;
};
bool operator<(const Point &x, const Point &y)
{
    return x.dis > y.dis;
}
priority_queue<Point> q;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
    }
    // dijkstra
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[s] = 0;
    q.push((Point){s, 0});
    for (int t = 1; t <= n - 1; t++)
    {
        // 找到当前距离最近且未确定的点
        while (!q.empty() && vis[q.top().id])
            q.pop();
        if (q.empty())
            break;
        int u = q.top().id;
        // u可以确定距离为 dis[u] 了
        vis[u] = true;
        // 用 u 优化其他点
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].v;
            int w = e[u][i].w;
            if (vis[v])
                continue;
            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                q.push((Point){v, dis[v]});
            }
        }
    }

    // 输出
    for (int i = 1; i <= n; i++)
    {
        if (dis[i] == 0x3f3f3f3f)
            cout << 2147483647 << " ";
        else
            cout << dis[i] << " ";
    }
    return 0;
}
    • 0
      @ 2023-1-17 10:21:49

      单源最短路径-弱化版

      floyd(40分) - O(n3)O(n^3)

      原始模式（dp）

      #include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
const int MAXM = 10000;
int n, m, s; // 点数、边数、出发点编号
struct Edge
{
    int v, w;
};
vector<Edge> e[MAXN + 5];
// dp[i][j][k]: 经过1~k这些点优化后的，i~j 的最短路
int dp[MAXN + 5][MAXN + 5][MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(dp, 0x3f, sizeof(dp));
    // 输入
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
        dp[u][v][0] = w;
    }
    for (int i = 1; i <= n; i++)
        dp[i][i][0] = 0;
    // floyd
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j][k] = min(dp[i][j][k - 1],
                                  dp[i][k][k - 1] + dp[k][j][k - 1]);

    // 输出
    for (int i = 1; i <= n; i++)
    {
        if (dp[s][i][n] == 0x3f3f3f3f)
            cout << 2147483647 << " ";
        else
            cout << dp[s][i][n] << " ";
    }
    return 0;
}

      一般模式（常写）

      #include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
const int MAXM = 10000;
int n, m, s; // 点数、边数、出发点编号
// dp[i][j][~k]: 经过1~k这些点优化后的，i~j 的最短路
int dp[MAXN + 5][MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(dp, 0x3f, sizeof(dp));
    // 输入
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        dp[u][v] = min(dp[u][v], w);
    }
    for (int i = 1; i <= n; i++)
        dp[i][i] = 0;
    // floyd
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = min(dp[i][j],
                               dp[i][k] + dp[k][j]);
    // 输出
    for (int i = 1; i <= n; i++)
    {
        if (dp[s][i] == 0x3f3f3f3f)
            cout << 2147483647 << " ";
        else
            cout << dp[s][i] << " ";
    }
    return 0;
}

      Bellman-ford（100 分）- O(nm)O(nm)

      #include <bits/stdc++.h>
using namespace std;
const int MAXN = 10'000;
const int MAXM = 500'000;
int n, m, s; // 点数、边数、出发点编号
int u[MAXM + 5], v[MAXM + 5], w[MAXM + 5];
int dis[MAXN + 5]; // dis[i]: s->i 的最短路
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
        cin >> u[i] >> v[i] >> w[i];

    // Bellman-ford
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    for (int t = 1; t <= n - 1; t++) // 做n-1轮
    {
        bool flag = false;
        for (int i = 1; i <= m; i++)
        {
            // u[i]->v[i] : w[i]
            if (dis[u[i]] + w[i] < dis[v[i]])
            {
                dis[v[i]] = dis[u[i]] + w[i];
                flag = true;
            }
        }
        if (!flag)
            break;
    }
    // 输出
    for (int i = 1; i <= n; i++)
    {
        if (dis[i] == 0x3f3f3f3f)
            cout << 2147483647 << " ";
        else
            cout << dis[i] << " ";
    }
    return 0;
}

      SPFA - O(n,m)O(n,m)

      #include <bits/stdc++.h>
using namespace std;
const int MAXN = 10'000;
const int MAXM = 500'000;
int n, m, s; // 点数、边数、出发点编号
struct Edge
{
    int v, w;
};
vector<Edge> e[MAXN + 5];
int dis[MAXN + 5];  // dis[i]: s->i 的最短路
bool vis[MAXN + 5]; // vis[i]: i号点在不在队列里
queue<int> q;       // 存储被优化过的点（尝试用它们作为起点的边优化边的终点）
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
    }
    // SPFA
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[s] = 0;
    q.push(s);
    vis[s] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false; // u点现在不在队列里了
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].v;
            int w = e[u][i].w;
            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                if (vis[v] == false)
                {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    // 输出
    for (int i = 1; i <= n; i++)
    {
        if (dis[i] == 0x3f3f3f3f)
            cout << 2147483647 << " ";
        else
            cout << dis[i] << " ";
    }
    return 0;
}

      Dijkstra-无优化版-O(n2+m)O(n^2+m)

      #include <bits/stdc++.h>
using namespace std;
const int MAXN = 10'000;
const int MAXM = 500'000;
int n, m, s; // 点数、边数、出发点编号
struct Edge
{
    int v, w;
};
vector<Edge> e[MAXN + 5];
int dis[MAXN + 5];  // dis[i]: s->i 的最短路
bool vis[MAXN + 5]; // vis[i]: i 号点是否已经确定了
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
    }
    // dijkstra
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[s] = 0;
    for (int t = 1; t <= n - 1; t++)
    {
        // 找到当前距离最近且未确定的点
        int u = -1;
        for (int i = 1; i <= n; i++)
        {
            if (vis[i])
                continue;
            if (u == -1 || dis[i] < dis[u])
                u = i;
        }
        if (u == -1)
            break;
        // u可以确定距离为 dis[u] 了
        vis[u] = true;
        // 用 u 优化其他点
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].v;
            int w = e[u][i].w;
            if (vis[v])
                continue;
            if (dis[u] + w < dis[v])
                dis[v] = dis[u] + w;
        }
    }

    // 输出
    for (int i = 1; i <= n; i++)
    {
        if (dis[i] == 0x3f3f3f3f)
            cout << 2147483647 << " ";
        else
            cout << dis[i] << " ";
    }
    return 0;
}
      • 1

      最短路 - 扩展题单

      信息

      ID
      1208
      时间
      1000ms
      内存
      256MiB
      难度
      3
      标签
      递交数
      22
      已通过
      19
      上传者
      1. 评测队列
      2. 服务状态
      3. 兼容模式
      4. 主题
      2. 陕ICP备2024054233号
      3. Worker 0, 55ms
      4. Powered by Hydro v4.18.1 Community, Modified by 33DAI