首页 > 代码库 > 洛谷 P1756 最小花费
洛谷 P1756 最小花费
题目背景
题目描述
在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。
输入输出格式
输入格式：
第一行输入两个正整数n,m，分别表示总人数和可以互相转账的人的对数。
以下m行每行输入三个正整数x,y,z，表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费 (z<100)。
最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账。
输出格式：
输出A使得B到账100元最少需要的总费用。精确到小数点后8位。
输入输出样例
输入样例#1：
3 3 1 2 12 3 21 3 31 3
输出样例#1：
103.07153164
说明
1<=n<=2000
AC代码：
N^2都能过，无语。。
1 #include<iostream> 2 #include<cstdio> 3 #define MAXN 2001 4 #define inf 99999 5 using namespace std; 6 int N,M,A,B; 7 double m[MAXN][MAXN]; 8 int main() 9 {10 int i,j;11 cin>>N>>M;12 cout.setf(ios::fixed);13 for (i=0;i<N;i++)14 for (j=0;j<N;j++)15 m[i][j]=1/inf;// 就这样来看是016 17 for (i=0;i<M;i++)18 {19 int x,y,t;20 cin>>x>>y>>t;21 x--; y--;22 m[x][y]=m[y][x]=1-(t/100.0);//转换成剩余百分之多少23 }24 25 cin>>A>>B;26 A--; B--;27 //dijkstra28 double dis[MAXN]; //dis i:money needed to trans 100 to i29 bool book[MAXN];30 book[B]=true;31 for (i=0;i<N;i++)32 {33 dis[i]=100/m[B][i]; //init dis[]34 book[i]=false; //init book[]35 }36 for (j=0;j<N;j++)37 {38 int nmin;39 double min=inf;40 for (i=0;i<N;i++)41 if (dis[i]<min&&!book[i])42 {43 nmin=i;44 min=dis[nmin]; //find #min->nmin45 }46 book[nmin]=true; //record in book[]47 for (i=0;i<N;i++)48 if (min/m[nmin][i]<dis[i]&&!book[i]) //relax49 dis[i]=min/m[nmin][i];50 }51 printf("%.8lf",dis[A]);52 return 0;53 }
80分代码存档：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #define N 2005 6 using namespace std; 7 int n,m,S,E,head[N],ei; 8 double dis[N]; 9 bool exist[N];10 struct node{11 int u,v,next;12 double w;13 }e[N*25];14 void add_edge(int u,int v,int x){15 double w=(double)x;w/=100;16 e[++ei].u=u;e[ei].v=v;e[ei].w=w;17 e[ei].next=head[u];head[u]=ei;18 }19 queue<int> q;20 void SPFA(){21 for(int i=1;i<=n;i++) dis[i]=99999999.0;22 memset(exist,false,sizeof(exist));23 exist[S]=true;q.push(S);dis[S]=100.0;24 while(!q.empty()){25 int p=q.front();q.pop();26 exist[p]=false;27 for(int i=head[p];i;i=e[i].next){28 int v=e[i].v;29 if(dis[v]>dis[p]/(e[i].w)){30 dis[v]=dis[p]/(e[i].w);31 if(!exist[v]){32 q.push(v);exist[v]=true;33 }34 }35 }36 }37 }38 int main()39 {40 scanf("%d%d",&n,&m);41 for(int i=1,u,v,w;i<=m;i++){42 scanf("%d%d%d",&u,&v,&w);43 add_edge(v,u,100-w);44 add_edge(u,v,100-w);45 }46 scanf("%d%d",&E,&S);47 SPFA();48 printf("%.8lf",dis[E]);49 return 0;50 }
刚开始用100往回乘（1+e[i].w）全错了，后来改成除了。。
思路：建立无向图（刚开始建成有向图了。。），跑最短路。。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 int n,m,S,E,head[15000],ei; 7 double dis[2100]; 8 bool exist[2010]; 9 struct node{10 int u,v,next;11 double w;12 }e[20000];13 void add_edge(int u,int v,int x){14 double w=(double)x;w/=100.0;15 e[++ei].u=u;e[ei].v=v;e[ei].w=w;16 e[ei].next=head[u];head[u]=ei;17 }18 queue<int> q;19 void SPFA(){20 for(int i=1;i<=n;i++) dis[i]=99999999.0;21 memset(exist,false,sizeof(exist));22 exist[S]=true;q.push(S);dis[S]=100.0;23 while(!q.empty()){24 int p=q.front();q.pop();25 exist[p]=false;26 for(int i=head[p];i;i=e[i].next){27 int v=e[i].v;28 if(dis[v]>dis[p]*(1.0+e[i].w)){29 dis[v]=dis[p]*(1.0+e[i].w);30 if(!exist[v]){31 q.push(v);exist[v]=true;32 }33 }34 }35 }36 }37 int main()38 {39 scanf("%d%d",&n,&m);40 for(int i=1,u,v,w;i<=m;i++){41 scanf("%d%d%d",&u,&v,&w);42 add_edge(v,u,w);43 add_edge(u,v,w);44 }45 scanf("%d%d",&E,&S);46 SPFA();47 printf("%.8lf",dis[E]);48 return 0;49 }
这样写不知道为什么结果总是整数部分正确，小数部分全是0，一时没看出哪里错了
洛谷 P1756 最小花费
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。