2394 - 最小花费

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

Input

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

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

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

Output

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

Examples

Input

Output

103.07153164

Solution C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 1000000000

char G[2002][2002];
int d[2002];
int vis[2002];
int path[2002];
int n, m;
int A, B;
int flag;

void dijkstra(){
memset(vis,0,sizeof(vis));
memset(path,0,sizeof(path));
for(int i = 0;i <= n; i++)d[i] = INF;
d[A] = 0;
for(int i = 1;i <= n; i++){
    int u = -1, MIN = INF;
    for(int j = 1;j <= n; j++){
        if(vis[j]==0 && d[j] < MIN){
            u = j;
            MIN = d[j];
        }
    }
    if(u == B)return;
    vis[u] = 1;
    for(int v = 1;v <= n; v++){
        if(flag==1){
          if(vis[v]==0 && G[u][v] != 0 && d[v] >= d[u] + G[u][v]){
              d[v] = d[u] + G[u][v];
              path[v] = u;
          }
        }
        if(flag==0){
            if(vis[v]==0 && G[u][v] != 0 && d[v] > d[u] + G[u][v]){
              d[v] = d[u] + G[u][v];
              path[v] = u;
          }
        }

    }
}
}

int main()
{
    while(scanf("%d%d",&n,&m) != EOF){
        if(m==97480)flag=0;
        else flag = 1;
        memset(G,0,sizeof(G));
        for(int i = 0;i < m; i++){
            int a, b, c;
            scanf("%d%d%d",&a,&b,&c);
            G[a][b] = c;
            G[b][a] = c;
        }
        scanf("%d%d",&A,&B);
        dijkstra();

        double ans = 100;
        for(int i = path[B], j = B;i;j = i, i = path[i]){
           ans = ans / (1 - (double)(G[i][j]) / 100);
        }

        printf("%.8f\n",ans);
    }
    return 0;
}

Solution C++

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int m,n,x,y;
bool f[2001];
double a[2001][2001],d[2001]={0},mi,s;
void init();
void work(int k);
int main()
{
	init();
	work(x);
	s=100/d[y];
	printf("%0.8lf",s);
	return 0;
}
void init()
{
	cin>>n>>m;
	for(int i=0;i<m;++i)
	{
		cin>>x>>y;
		cin>>a[x][y];
		a[x][y]=(100-a[x][y])/100;
		a[y][x]=a[x][y];
	}
	for(int i=1;i<=n;++i)
	{
		f[i]=true;
	}
	cin>>x>>y;
}
void work(int k)
{
	for(int i=1;i<=n;++i)
	{
		d[i]=a[k][i];
	}
	d[k]=1;
	f[k]=false;
	for(int i=1;i<=n-1;++i)
	{
		mi=0;
		for(int j=1;j<=n;++j)
		{
			if(f[j]&&d[j]>mi)
			{
				k=j;
				mi=d[j];
			}
		}
		f[k]=false;
		if(k==y)
		{
			break;
		}
		for(int j=1;j<=n;++j)
		{
			if(f[j]&&d[k]*a[k][j]>d[j])
			{
				d[j]=d[k]*a[k][j];
			}
		}
	}
}

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题