洛谷题单——【图论2-2】最短路

P3371 【模板】单源最短路径（弱化版）

堆优化版 dijkstra轻松搞定，可以过两题（手动狗头）

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m, s;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra(int s)
{
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<PII, vector<PII>, greater<PII> > heap; //> >不能连在一起
    dist[s] = 0;
    heap.push({0, s});
    while (heap.size())
    {
        PII t = heap.top(); //洛谷不能编译auto类型
        heap.pop();
        int ver = t.second, distance = t.first;
        if (st[ver])
            continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s;
    memset(h, -1, sizeof(h));
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    dijkstra(s);
    int t = 2147483647;
    for (int i = 1; i <= n; i++)
    {
        if (dist[i] == 0x3f3f3f3f)
            cout << t << " ";
        else
            cout << dist[i] << " ";
    }
    cout << endl;
    return 0;
}

P1629 邮递员送信

这道题一开始想直接用Floyd算法求出多源汇最短路，一看数据范围直接放弃
这道题只需要先正向建图再反向建图
正向建图求出1号点到其他点的最短路
反向建图求1号点到其他点的最短路就是其他所有点到1号点的最短路
我的代码直接用朴素版 dijkstra算法求解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+10;
int n, op;
int g1[N][N], dist1[N];
bool st1[N];
int g2[N][N], dist2[N];
bool st2[N];
void dijkstra1()
{
    memset(dist1, 0x3f, sizeof(dist1));
    dist1[1] = 0;
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
        {
            if (!st1[j] && (t == -1 || dist1[t] > dist1[j]))
                t = j;
        }
        st1[t] = true;
        for (int j = 1; j <= n; j++)
            dist1[j] = min(dist1[j], dist1[t] + g1[t][j]);
    }
}
void dijkstra2()
{
    memset(dist2, 0x3f, sizeof(dist2));
    dist2[1] = 0;
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
        {
            if (!st2[j] && (t == -1 || dist2[t] > dist2[j]))
                t = j;
        }
        st2[t] = true;
        for (int j = 1; j <= n; j++)
            dist2[j] = min(dist2[j], dist2[t] + g2[t][j]);
    }
}
int main()
{
    cin >> n >> op;
    //注意建图一定要先进行初始化
    memset(g1, 0x3f, sizeof(g1));
    memset(g2, 0x3f, sizeof(g2));
    while (op--)
    {
        int a, b, w;
        cin >> a >> b >> w;
        g1[a][b] = min(g1[a][b], w);
        g2[b][a] = min(g2[b][a], w);
    }
    dijkstra1();
    dijkstra2();
    ll res = 0;
    for (int i = 2; i <= n; i++)
        res = res + dist1[i] + dist2[i];
    printf("%ld\n",res);
    return 0;
}

最短路计数

并没有什么太大的难度，只需要在进行spfa算法是的时，加上一个最短路计数器即可
主要要搞明白什么时候最短路的数量会被更新
1、当这个点的距离被更新时，这个点的最短路数量等于更新它点的最短路的数量
2、当这个点的距离等于更新它点的距离加上两点之间的权值时，说明最短路不只一条，此时需要这个点最短路的数量是两个点最短路数量的叠加

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, M = 3 * 1e6 + 10, MOD = 100003;
int h[N], e[M], ne[M], idx;
int n, m;
int dist[N];
bool st[N];
int ans[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void spfa() //正常的spfa算法中加入计数功能
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    queue<int> vis;
    vis.push(1);
    st[1] = true;
    ans[1] = 1; //自己到自己的最短路只有一条
    while (vis.size())
    {
        int t = vis.front();
        vis.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + 1) //如果这个点的距离可以被更新
            {
                ans[j] = ans[t]; //这个点的最短路数量等于更新它的点的最短路的数量
                dist[j] = dist[t] + 1;
                if (!st[j])
                {
                    vis.push(j);
                    st[j] = true;
                }
            }
            else if (dist[j] == dist[t] + 1) //如果这个点的距离等于更新它点的距离+1，说明最短路不只有一条
            {
                ans[j] += ans[t]; //这个点的最短路数量要加上更新它点的最短路的数量
                ans[j] %= MOD;
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    spfa();
    for (int i = 1; i <= n; i++)
        cout << ans[i] << endl;
    return 0;
}

灾后重建

刷了这道题以后对floyd算法有了更深的理解
首先对于floyd

void floyd() //直接将邻接矩阵更新成a到b的最短路
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

这个算法只有短短几行完成了多源汇最短路就求解
这道题需要对floyd算法的原理有一定的了解
floyd算法的第一重循环即表示在求解节点i到节点j的最短路的路程中最多只经过前k个点

和这道题中所给的条件非常类似
这道题不就是按顺序遍历所有的已经重建好的村庄
而且题中给的村庄的建成时间还是单调不减序列，都省去了排序的步骤
在所给的Q个询问中给出的时间序列还是单调不减的
有了这两个条件能让我们很好的应用floyd算法来解决这个问题

#include <bits/stdc++.h>
using namespace std;
const int N = 210, INF = 1e9;
int g[N][N];
int tim[N];
int n, m, op;
void floyd(int k)
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d", &tim[i]);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j)
                g[i][j] = 0;
            else
                g[i][j] = INF;
        }
    }
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = c;
    }

    scanf("%d", &op);
    int nt = 0;
    while (op--)
    {
        int x, y, t;
        scanf("%d%d%d", &x, &y, &t);
        if (tim[x] > t || tim[y] > t)
            cout << "-1" << endl;
        else
        {
            while (tim[nt] <= t && nt < n)
            {
                floyd(nt);
                nt++;
            }
            if (g[x][y] == INF)
                cout << "-1" << endl;
            else
                cout << g[x][y] << endl;
        }
    }
    return 0;
}

通往奥格瑞玛的道路

这道题目中要求所经过的所有城市中最多的一次收取的费用的最小值是多少
就是指以当前的血量经过最多的城市，在经过城市最多的条件下，求路费最少
这是典型的最大值最小问题，典型的二分法
并且是一道图论的题，因此算法只需要最短路算法+二分即可
根据时间复杂度，选择 dijkstra时间复杂度在1e8有些冒险，所以使用spfa算法求最短路
只需要对题目中的路费进行二分
很明显在这里二分的左边界是点权的最小值，有边界是点权的最大值
但是二分的范围只能在给定的点权中取值，也就是说只能在已经排序好的数组中取值
判断在当前路费的条件下，歪嘴不死（血量不被扣完）就可以

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10, INF = 0x3f3f3f3f;
int n, m, b;
//维护边权
int h[N], e[M], ne[M], w[N], idx;
int dist[N];
bool st[N];
//维护点权
int money[N];
int sortmon[N];
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool checkspfa(int k)
{
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0, sizeof(st));
    queue<int> vis;
    dist[1] = 0;
    vis.push(1);
    st[1] = true;
    while (vis.size())
    {
        int t = vis.front();
        vis.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i] && money[j] <= k) //在这里检查这个点的权值是不是小于等于二分得到的最大权值
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    vis.push(j);
                    st[j] = true;
                }
            }
        }
    }
    if (dist[n] <= b)
        return true;
    else
        return false;
}
int main()
{
    cin >> n >> m >> b;
    memset(h, -1, sizeof(h));
    for (int i = 1; i <= n; i++)
    {
        cin >> money[i];
        sortmon[i] = money[i];
    }
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    sort(sortmon + 1, sortmon + 1 + n);
    if (!checkspfa(INF))
        cout << "AFK" << endl;
    else
    {
        int l = 1, r = n;
        int ans = 0;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (checkspfa(sortmon[mid]))
            {
            	//二分在这里真是玄学编程，作为答案只能随时更新，二分结束之后再进行取值就会发生错误
                ans = sortmon[mid];
                r = mid;
            }
            else
                l = mid + 1;
        }
        cout << ans << endl;
    }
    return 0;
}