AcWing 1126. 最小花费

题目传送门

一、SPFA

#include
using namespace std;

const int N = 2010;     //点数,看的出来，点数不多，采用邻接矩阵也OK
const int M = 2e5 + 10; //边数
//如果本题想要卡SPFA,也可以卡的死死的，因为最差的是O(n*m)=4e8

int n;          // n个节点
int m;          // m条边
double dist[N]; //从A点出发，到达每个点的最大距离
bool st[N];     //点i是不是已经进入队列

//链接前向星，注意double类型
int h[N], e[M], ne[M], idx;
double w[M];
void add(int a, int b, double c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
//从start出发
void spfa(int start) {
    queue q;
    dist[start] = 1; // 剩余的百分比(想像一下手机电池，目前是100%状态出发)
    q.push(start);
    st[start] = true; //标识在队列中
    while (q.size()) {
        int u = q.front(); //取出当前要处理的节点
        q.pop();
        st[u] = false; // u节点出队列
        //枚举u节点的每一条出边
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];                //对方节点号j
            double a = 1 - w[i];         // 100%减去消耗率，得到本路径的剩余率,需要与带过的数据连乘
            if (dist[j] < dist[u] * a) { //利用u更新j的路径最大值
                dist[j] = dist[u] * a;
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        double w = c * 0.01; //消耗的百分比,举例:从A->B的消耗百分比为2%
        add(a, b, w), add(b, a, w);
    }

    int A, B;
    cin >> A >> B;
    spfa(A);
    // ∵ x *w1*w2*w3* ... = 100
    // ∴ x = 100/(w1 * w2 * w3 * ...)
    // dist[B]装的就是从A点出发，到B点的 w1*w2*w3*...的连乘积
    printf("%.8lf\n", 100 / dist[B]);
    return 0;
}

二、Dijkstra+堆优化

#include 
using namespace std;

const int N = 2010;     //点数,看的出来，点数不多，采用邻接矩阵也OK
const int M = 2e5 + 10; //边数
//如果本题想要卡SPFA,也可以卡的死死的，因为最差的是O(n*m)=4e8

typedef pair PDI;

int n;          // n个节点
int m;          // m条边
double dist[N]; //从A点出发，到达每个点的最大距离
bool st[N];     //点i是不是已经进入队列

int h[N], e[M], ne[M], idx;
double w[M];
void add(int a, int b, double c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra(int start) {
    priority_queue q; //最长路径，用大根堆
    dist[start] = 1;       //剩余的百分比(想像一下手机电池，目前是100%状态出发)
    q.push({1, start});    //大根堆，按距离最大到小排序

    while (q.size()) {
        auto t = q.top();
        q.pop();
        int u = t.second;

        if (!st[u]) {
            st[u] = true;
            for (int i = h[u]; ~i; i = ne[i]) {
                int j = e[i];
                double a = 1 - w[i];         // 100%减去消耗率，得到本路径的剩余率,需要与带过的数据连乘
                if (dist[j] < dist[u] * a) { //利用u更新j的路径最大值
                    dist[j] = dist[u] * a;
                    q.push({dist[j], j});
                }
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        double w = c * 0.01; //消耗的百分比,举例:从A->B的消耗百分比为2%
        add(a, b, w), add(b, a, w);
    }

    int A, B;
    cin >> A >> B;

    dijkstra(A);
    // ∵ x *w1*w2*w3* ... = 100
    // ∴ x = 100/(w1 * w2 * w3 * ...)
    // dist[B]装的就是从A点出发，到B点的 w1*w2*w3*...的连乘积
    printf("%.8lf\n", 100 / dist[B]);
    return 0;
}