题解 P1576 【最小花费】

· · 题解

很裸的一道最“短”路问题，因为1<=n<=2000并且不存在负边权的情况，所以迪杰斯特拉也可以做，下面给出SPFA做法

首先我们可以发现两个人之间实际的汇率是 1-z% 那么我们就可以将人抽象成点，把两个人之间的汇率记做边权

如果A到B的汇率是 x ,B到C的汇率是y那么A到C的汇率就是x*y,所以原来SPFA模板中更新权值就可以改成乘的形式

因为最后要求出最少的汇款，所以就要求A与B之间的汇率最大，那么现在就很显然了

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,m,A,B,cnt;
double dis[2005],head[2005];//dis数组存的是起点到其余每个点的汇率 
bool vis[2005];
struct node//结构体邻接表存图 
{
    int to,next;
    double val;
}edge[1000005];//边数具体的大小没说，所以一开始开小结构体数组Re了两次 TAT，这里开1000000肯定能过 
void add(int x,int y,double z)
{
    cnt++;
    edge[cnt].to=y;
    edge[cnt].val=1-z;
    edge[cnt].next=head[x];
    head[x]=cnt;
}
void spfa()
{
    int u,v;
    queue<int>q;
    q.push(A);
    dis[A]=1;//起点与它本身的汇率是1 
    vis[A]=true;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=head[u];i;i=edge[i].next)
        {
            v=edge[i].to;
            if(dis[v]<dis[u]*edge[i].val)//依次更新最大汇率 
            {
                dis[v]=dis[u]*edge[i].val;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=true;
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    fill(dis+1,dis+n+1,0);//因为存的是最大汇率所以将dis数组初始化为一个小的数，但是涉及到了乘法所以不能设为负数，初始化为0即可 
    for(int x,y,z,i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,(double)z/100);//将z转化成小数 
        add(y,x,(double)z/100);
    }
    scanf("%d%d",&A,&B);
    spfa();
    printf("%.8lf",100/dis[B]);//用100除以最大的汇率就是最少需要汇多少钱 
    return 0;

}//其实这道题只是模板的一个小小的变通，还是很简单的^-^ //最后祝各位以及自己 NOIP2017 RP++