P1576 最小花費，P1576花費
題目背景
題目描述
在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 1
2 3 2
1 3 3
1 3
輸出樣例#1：
103.07153164
說明
1<=n<=2000
思路：一開始乖乖的打了個Dijkstra記錄路徑然後慢慢求最後才發現好扯淡也就能過個樣例
正確做法是求出每個邊的權重然後直接暴力
注意因為有除法的存在所以大於號小於號可能和平常的Dijkstra相反
0分代碼
![]()
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 using namespace std;
5 int map[3000][3000];
6 double money=100;
7 int dis[3000];
8 int maxn=0x7fffff;
9 int pass[3000];
10 int vis[3000];
11 int n,m;
12 int ans[1001];
13 void print(int bg,int ed)
14 {
15
16 int now=1;
17 ans[now]=ed;
18 now++;
19 int tmp=pass[bg];
20 while(tmp!=ed&&tmp!=0)
21 {
22 ans[now]=tmp;
23 now++;
24 tmp=pass[tmp];
25 }
26 ans[now]=bg;
27 int qq=ed;
28 for(int i=2;i<=now;i++)
29 {
30 money=money/((double)(100-map[ans[i-1]][ans[i]])/100);
31 }
32 printf("%.8lf",money);
33 }
34 void Dijkstra(int p)
35 {
36 memset(dis,0x7f,sizeof(dis));
37 vis[p]=1;
38 for(int i=1;i<=n;i++)
39 {
40 dis[i]=map[p][i];
41 }
42 for(int i=1;i<=n;i++)
43 {
44 int minn=maxn;
45 int k;
46 for(int j=1;j<=n;j++)
47 {
48 if(vis[j]==0&&dis[j]<minn)
49 {
50 minn=dis[j];
51 k=j;
52 }
53 }
54 vis[k]=1;
55 for(int j=1;j<=n;j++)
56 {
57 if(dis[j]>dis[k]+map[k][j])
58 {
59 dis[j]=dis[k]+map[k][j];
60 pass[j]=k;
61 }
62 }
63 }
64 }
65 int main()
66 {
67 memset(map,0x7f,sizeof(map));
68 scanf("%d%d",&n,&m);
69 for(int i=1;i<=n;i++)
70 {
71 int x,y,z;
72 scanf("%d%d%d",&x,&y,&z);
73 map[x][y]=z;
74 map[y][x]=z;
75 }
76 int a,b;
77 scanf("%d%d",&a,&b);
78 Dijkstra(b);
79 print(b,a);
80 return 0;
81 }
View Code
AC代碼
![]()
1 #include<iostream>
2 #define MAXN 2001
3 #define inf 99999
4 using namespace std;
5 int N,M,A,B;
6 double m[MAXN][MAXN];
7 int main()
8 {
9 int i,j;
10 cin>>N>>M;
11 cout.setf(ios::fixed);
12 for (i=0;i<N;i++)
13 for (j=0;j<N;j++)
14 m[i][j]=1/inf;
15 for (i=0;i<M;i++)
16 {
17 int x,y,t;
18 cin>>x>>y>>t;
19 x--; y--;
20 m[x][y]=m[y][x]=1-(t/100.0); //exchange to weight
21 }
22 cin>>A>>B;
23 A--; B--;
24 //dijkstra
25 double dis[MAXN]; //dis i:money needed to trans 100 to i
26 bool book[MAXN];
27 book[B]=true;
28 for (i=0;i<N;i++)
29 {
30 dis[i]=100/m[B][i]; //init dis[]
31 book[i]=false; //init book[]
32 }
33 for (j=0;j<N;j++)
34 {
35 int nmin;
36 double min=inf;
37 for (i=0;i<N;i++)
38 if (dis[i]<min&&!book[i])
39 {
40 nmin=i;
41 min=dis[nmin]; //find #min->nmin
42 }
43 book[nmin]=true; //record in book[]
44 for (i=0;i<N;i++)
45 if (min/m[nmin][i]<dis[i]&&!book[i]) //relax
46 dis[i]=min/m[nmin][i];
47 }
48 cout.precision(8);
49 cout<<dis[A];
50 return 0;
51 }
View Code
