1 条题解
-
1
最小花费题解
转化题意为从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; }
信息
- ID
- 844
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 44
- 已通过
- 13
- 上传者