【蓝桥-大试牛刀7-最短路专场】题解

最短路1

floyd说白了就是个暴力，用三层循环枚举所有路径，然后留下权值最小的一条

大概就长这个样

for(中转点k)
	for(起点i)
		for(终点j)
			d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

注意这个题的数据有重边，输入的时候留下最小的，这样就做完了

int d[N][N];

void solve()
{
    memset(d, 0x3f, sizeof d);

    int n, m;cin >> n >> m;
    for(int i = 1; i <= m; ++ i)
    {
        int u, v, w;cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);
        d[v][u] = min(d[v][u], w);
    }

    for(int i = 1; i <= n; ++ i)d[i][i] = 0;

    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]);

    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= n; ++ j)
        {
            if(d[i][j] <= inf)cout << d[i][j] << ' ';
            else cout << -1 << '\n';
        }
        cout << '\n';
    }
}

最短路2

之前发的那个提示第一步操作其实没说全，这次来个全的。

1.re-weight

重新调整每一条边的权值。

建立一个编号为0的点，与所有节点相连，且权值为0，然后用Bellman-Ford求0号节点到所有点的最短路。

如果不存在负环，我们就得到了一个\(h[]\)数组，接下来修改每条边的权值\(w(u,v)=w(u,v)+h[u]-h[v]\)

2.dijkstra

在此基础上对每个点跑单源最短路，注意边权已经改变，最后要进行还原

\(d(u,v)=d(u,w)-h[u]+h[v]\)

struct node
{
    ll x, w;
    bool operator < (const node &u)const
    {
        return w == u.w ? x < u.x : w > u.w;
    }
};
vector<node> g[N];

int n, m;

ll h[N], d[N][N];

bool spfa(int st)
{
    //初始化
    for(int i = 1; i <= n; ++ i)h[i] = inf;
    bitset<N> inq;
    queue<int> q;
    vector<int> cnt(n + 1);
    q.push(st);
    inq[st] = true;

    while(!q.empty())
    {
        auto x = q.front();q.pop();inq[x] = false;
        for(const auto &[y, w] : g[x])
        {
            if(h[x] + w < h[y])
            {
                if(++ cnt[y] >= n)return true;
                h[y] = h[x] + w;
                if(!inq[y])q.push(y), inq[y] = true;
            }
        }
    }
    return false;
}

void dijkstra(int st, ll d[])
{
    for(int i = 1; i <= n; ++ i)d[i] = inf;
    priority_queue<node> pq;
    bitset<N> vis;
    pq.push({st, d[st] = 0});
    while(!pq.empty())
    {
        auto x = pq.top().x;pq.pop();
        if(vis[x])continue;
        vis[x] = true;
        for(const auto &[y, w] : g[x])
        {
            if(d[y] > d[x] + w)
            {
                d[y] = d[x] + w;
                pq.push({y, d[y]});
            }
        }
    }

    //还原
    for(int i = 1; i <= n; ++ i)d[i] = d[i] - h[st] + h[i];
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= m; ++ i)
    {
        ll u, v, w;cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    //1.建立虚拟原点
    for(int i = 1; i <= n; ++ i)g[0].push_back({i, 0}), h[i] = inf;

    //2.Bellman-Ford求0点到所有点的最短路，作为势能h[]
    if(spfa(0))
    {
        cout << "Ciallo~" << '\n';
        return;
    }

    //3.改造所有边
    for(int x = 1; x <= n; ++ x)
    {
        for(auto &[y, w] : g[x])w = w + h[x] - h[y];
    }

    //4.跑n次dijkstra
    for(int i = 1; i <= n; ++ i)dijkstra(i, d[i]);

    int q;cin >> q;
    while(q --)
    {
        int x, y;cin >> x >> y;
        if(d[x][y] > inf / 2)cout << 114514 << '\n';
        else cout << d[x][y] << '\n';
    }
}

最短路3

如果看过提示应该是可以做出来的吧

这里直接给完整代码了

int n, m;
ll d[N];
ll cnt[N];

vector<int> g[N];

void bfs(int st)
{
    memset(d, 0x3f, sizeof d);
    bitset<N> vis;
    queue<int> q;
    q.push(1);
    d[st] = 0, cnt[st] = 1, vis[st] = true;

    while(!q.empty())
    {
        auto x = q.front();q.pop();
        for(const auto &y : g[x])
        {
            if(!vis[y])
            {
                q.push(y);
                vis[y] = true;
                d[y] = d[x] + 1;
                cnt[y] = cnt[x];
            }else if(d[y] == d[x] + 1)
            {
                cnt[y] = cnt[y] + cnt[x];
            }
        }
    }
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= m; ++ i)
    {
        int u, v, w;cin >> u >> v >> w;
        g[u].push_back(v), g[v].push_back(u);
    }
    bfs(1);
    for(int i = 1; i <= n; ++ i)cout << cnt[i] << " \n"[i == n];
}