-----------------------------------
这道题就是图论最短路，但是我们要改一下一些细节
比如说，因为这是算汇率，我们的初始化就要是0
我们还要改一改松弛操作
-----------------------------------
还有，题目上给的是汇率（而且是整形）
所以说我们要改成小数
-----------------------------------
以及，汇率是我们在操作中的“损失”
那么，我们留下的部分就是1-汇率（易得）
----------------------------------
DOUBLE警告
----------------------------------
以上就是特别注意
其实还有坑的数据范围100000的数组只能RE
----------------------------------
题目链接:Miku
----------------------------------
#include<iostream> #include<queue> #include<stack> #include<algorithm> #include<cstring> using namespace std; int n,m; struct bian { int to; int next; double v; //注意，是double } b[1000010]; double dis[1000010];//double警告 queue<int> q; int head[1000001]; int pb; void add(int form,int to,double v) {//double警告 pb++; b[pb].to=to; b[pb].v=1-v;//省很多事的 b[pb].next=head[form]; head[form]=pb; } bool vis[1000001]; int main() { memset(dis,0,sizeof(dis)); cin>>n>>m; int x,y,z; for(int i=1; i<=m; ++i) { cin>>x>>y>>z; add(x,y,(double)z/100); add(y,x,(double)z/100);//一定要处理成小数 } cin>>x>>y; { //SPFA部分 dis[x]=1; vis[x]=1; q.push(x);//初始化 { while(q.size()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u]; i; i=b[i].next) { int v=b[i].to; if(dis[v]<dis[u]*b[i].v) {//特殊操作 dis[v]=dis[u]*b[i].v;//特殊操作 { if(!vis[v]) { q.push(v); vis[v]=1; } } } } } } } double ans=100/dis[y];//double警告 printf("%.8lf",ans);//小数位数哦 return 0; }
------------------------------------
That's all.