洛谷1073 最优贸易

最短路

原题链接

以\(1\)为起点在正图上跑\(SPFA\)或\(Dijkstra\)，求出\(dis1[x]\)，表示从\(1\)到节点\(x\)的所有路径中，经过权值最小的节点的权值；再以\(n\)为起点在反图上跑\(SPFA\)或\(Dijkstra\)，求出\(dis2[x]\)，表示从\(n\)到节点\(x\)的所有路径中，经过权值最大的节点的权值。
最后枚举节点，求\(max\{dis2[x]-dis1[x]\}\)即可。

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
const int M = 5e5 + 10;
int fi[N], di[M << 1], pr[N], ne[M << 1], dis[N], disf[N], fif[N], dif[M << 1], nef[M << 1], q[M << 1], l, lf;
bool v[N];
int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c<'0' || c>'9'; c = getchar())
        p |= c == '-';
    for (; c >= '0'&&c <= '9'; c = getchar())
        x = x * 10 + (c - '0');
    return p ? -x : x;
}
inline void add(int x, int y)
{
    di[++l] = y;
    ne[l] = fi[x];
    fi[x] = l;
}
inline void addf(int x, int y)
{
    dif[++lf] = y;
    nef[lf] = fif[x];
    fif[x] = lf;
}
inline int minn(int x, int y)
{
    return x < y ? x : y;
}
inline int maxn(int x, int y)
{
    return x > y ? x : y;
}
int main()
{
    int i, n, m, x, y, head = 0, tail = 1, ma = 0;
    n = re();
    m = re();
    for (i = 1; i <= n; i++)
        pr[i] = re();
    for (i = 1; i <= m; i++)
    {
        x = re();
        y = re();
        if (re() == 1)
        {
            add(x, y);
            addf(y, x);
        }
        else
        {
            add(x, y);
            add(y, x);
            addf(x, y);
            addf(y, x);
        }
    }
    memset(dis, 60, sizeof(dis));
    q[1] = 1;
    dis[1] = pr[1];
    while (head != tail)
    {
        x = q[++head];
        v[x] = 0;
        for (i = fi[x]; i; i = ne[i])
        {
            y = di[i];
            if (dis[y] > minn(dis[x], pr[y]))
            {
                dis[y] = minn(dis[x], pr[y]);
                if (!v[y])
                {
                    q[++tail] = y;
                    v[y] = 1;
                }
            }
        }
    }
    memset(v, 0, sizeof(v));
    head = 0;
    tail = 1;
    q[1] = n;
    disf[n] = pr[n];
    while (head != tail)
    {
        x = q[++head];
        v[x] = 0;
        for (i = fif[x]; i; i = nef[i])
        {
            y = dif[i];
            if (disf[y] < maxn(disf[x], pr[y]))
            {
                disf[y] = maxn(disf[x], pr[y]);
                if (!v[y])
                {
                    q[++tail] = y;
                    v[y] = 1;
                }
            }
        }
    }
    for (i = 1; i <= n; i++)
        ma = maxn(ma, disf[i] - dis[i]);
    printf("%d", ma);
    return 0;
}

ps：因为我用的是\(VS\)，所以代码会自动补空格，而我本来的风格是没有空格的。

洛谷1073 最优贸易

原文：https://www.cnblogs.com/Iowa-Battleship/p/9535215.html