WUST 1934 最小花费（最短路+迪杰斯特拉）

红太狼 2022-06-12 13:48 180阅读 0赞

## 1934: 最小花费 ##

Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld  
Submitted: 8 Accepted: 6  
\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

## Description ##

在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。

## Input ##

多组测试数据。

第一行输入两个正整数n,m，分别表示总人数和可以互相转账的人的对数。1<=n<=2000

以下m行每行输入三个正整数x,y,z，表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费 (z<100)。

最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账。

## Output ##

输出A使得B到账100元最少需要的总费用。精确到小数点后8位。

## Sample Input ![copy.gif][]           ##

3 3
    1 2 1
    2 3 2
    1 3 3
    1 3

## Sample Output ##

103.07153164

\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

题解：

由于是点较多，所以选择迪杰斯特拉算法，题目是迪杰斯特拉算法的变形，松弛的条件变了，算是最短路练习吧

代码：

#include<iostream>
    #include<stdio.h>
    #include<map>
    #include<algorithm>
    #include<math.h>
    #include<queue>
    #include<stack>
    #include<string>
    #include<cstring>
    using namespace std;
    const int INF=10086111;
    int p[2005][2005];//保存路径
    double dis[2005];//起始点点到其他点的距离
    int vis[2005];//判断是否遍历的数组
    int main()
    {
        int i,j,k,n,m,x,y,d;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            memset(vis,0,sizeof(vis));
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                    p[i][j]=INF;//开始初始化
            }
            for(i=0;i<m;i++)
            {
                scanf("%d%d%d",&x,&y,&d);
                p[x][y]=d;
                p[y][x]=d;
            }
            scanf("%d%d",&x,&y);
            for(i=1;i<=n;i++)
            {
                if(p[x][i]==INF)//要特判是否有通路
                    dis[i]=INF;
                else
                    dis[i]=100*100/(double)(100-p[x][i]);
            }
            vis[x]=1;//标记
            for(i=1;i<n;i++)
            {
                int key;
                double minn=INF;
                for(j=1;j<=n;j++)
                {
                    if(!vis[j]&&dis[j]<minn)//找一个最小的且没有标记过的
                    {
                        key=j;
                        minn=dis[j];
                    }
                }
                vis[key]=1;//标记
                for(j=1;j<=n;j++)
                {
                    if(p[key][j]==INF)//很重要
                        continue;
                    if(minn*100/(double)(100-p[key][j])<dis[j])//松弛操作的条件变化了，因为算路径长度的方法变了
                        dis[j]=minn*100/(double)(100-p[key][j]);
                }
            }
            printf("%.8lf\n",dis[y]);
        }
        return 0;
    }

[Submit]: http://acm.wust.edu.cn/submitpage.php?id=1934&soj=0
[Status]: http://acm.wust.edu.cn/problemstatus.php?id=1934&soj=0
[Web Board]: http://acm.wust.edu.cn/bbs.php?pid=1934&soj=0
[copy.gif]: http://acm.wust.edu.cn/image/copy.gif