P3001题解

The_BJX · 2021-08-19 11:42:05 · 题解

前言

瞎写了个 SPFA 就切掉了。
其他题解都 WA 了。所以我写了个正确的。

题意简述

求有向图上的最短路，路径的权值为经过的所有边的权值之和。

有人因为没发现是有向图而 WA 掉了。

为什么要用 SPFA？

看到图上求权值最小的路径之类的问题时，可以很容易想到需要最短路算法。

此题的距离依照题意，就是边权的乘积。因此将松弛部分改一下即可。

因此这里的负环指的是一个边权之积小于 1 的环。如果一直沿着这个环走，价格就会越走越低,没有最小值（最后就可以白嫖了）。所以此题要判负环。然而我只会 SPFA。

AC 代码：

#include <iostream>
#include <iomanip>
#include <cstring>
#include <queue>
#define ll long double//用 long double 不然会被卡精度去世
using namespace std;
const ll inf = 9982443500;
struct edge{
    int to;
    int next;
    ll w;
}edges[600000];
int head[30000];
int tot;
void add(int a, int b, ll w)
{
    edges[++tot].to=b;
    edges[tot].w=w;
    edges[tot].next=head[a];
    head[a]=tot;
}//前向星基操

int n,m,a,b;
ll v;
queue<int> sp;//SPFA 的主队列
bool in[30000];//某一个点是否现在在队列里
int count[30000];//各店入队的次数
ll dis[30000];//源点到各店的距离

void push(int x)
{
    if(!in[x])
    {
        sp.push(x);
        in[x]=true;
        count[x]++;
    }
}

bool spfa(int f)
{
    while(!sp.empty())sp.pop();
    push(f);
    dis[f]=1;
    while(!sp.empty())
    {
        int x=sp.front();
        sp.pop();
        in[x]=false;
        for (int i = head[x]; i; i=edges[i].next)
        {
            int y=edges[i].to;
            if(dis[y]>dis[x]*edges[i].w)
            {
                dis[y]=dis[x]*edges[i].w;//注意是乘积！ 
                if(!in[y])
                {
                    push(y);
                    if(count[y]>n)
                    {
                        return true;
                        //判断负环，如果入队次数大于点数说明有负环
                    }
                }
            }
        }
    }
    return false;
}

int main()
{

    cin >> n >> m >> v >> a >> b;
    for (int i = 1; i <= n; i++)
    {
        dis[i]=inf;
    }
    for (int i = 0; i < m; i++)
    {
        int u,v;
        ll w;
        cin >> u >> v >> w;
        add(u,v,w);
    }

    if(spfa(a))cout << 0;
    else cout << fixed << setprecision(6) << dis[b]*v;//记得乘原价

}

蒟蒻的第一篇题解求过 qwq 啊啊啊!