最小花费题解

转化题意为从A出发，寻找到达B点且手续费最低的路径

数据范围 1<=n<=2000,m<=100000 数据量逆推可知最大差不多允许使用O(n^2)或者O(n^2(logn))的算法 经典dijkstra板子题，用不用堆优化都行，不优化时间复杂度为O(n^2^),优化后时间复杂度为O(mlogn) 注意数据范围，数组因为是双向边，边的范围要乘2倍 附代码与详细注释

#include <bits/stdc++.h>
using namespace std;
typedef pair<double,int> PDI;

const int N=2e5+1000;
const double M=1e-8;

int n,m,A,B;
//边数远大于节点数，为稀疏图，用邻接表存
int h[N],e[N*2],ne[N*2],w[N*2],idx;
double dist[N];
bool st[N];
priority_queue<PDI>pq;//大根堆
//first存保留比例，second存节点编号

//加边和对应手续费
void add(int a,int b,int z)
{
    e[idx]=b,w[idx]=z,ne[idx]=h[a],h[a]=idx++;
}
//堆优化版dijkstra
double dijstra()
{
    memset(dist,0,sizeof dist);
    pq.push({1.0,A});//无手续费
    dist[A]=1.0;
    while(!pq.empty())
    {
        auto t=pq.top();
        pq.pop();
        double distance=t.first;
        int p=t.second;
        if(distance<dist[p]-M)
            continue;
        if(st[p])
            continue;
        if(p==B)break;
        st[p]=true;//标记当前节点已确定为最优
        for(int i=h[p];i!=-1;i=ne[i])//遍历他连的边
        {
            int j=e[i];
            int z=w[i];//扣除z%手续费
            //新的保留比例
            double res=distance*(100.0-z)/100.0;
            if(res>dist[j]+M)//更合适
            {
                dist[j]=res;
                pq.push({res,j});
            }
        }
    }
    return 100.0/dist[B];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    memset(h,-1,sizeof h);//初始化头结点
    while(m--)
    {
        int a,b,z;
        cin>>a>>b>>z;
        //用单向边存双向边
        add(a,b,z);
        add(b,a,z);
    }
    cin>>A>>B;
    if(A==B)
    {
        cout<<100.00000000<<endl;
        return 0;
    }
    double res=dijstra();
    cout<<fixed<<setprecision(8)<<res<<'\n';
    return 0;
}