P1576代码不知怎么回事错了
查看原帖
P1576代码不知怎么回事错了
1531031
songyuteng楼主2024/12/19 19:57
#include<bits/stdc++.h>
using namespace std;
int a[2010][2010];//邻接矩阵
int n,m,s,e; //s,e表示起止点start,end.
//反推要使得B得到100元,那么每个点至少要汇出多少钱
double d[2010];
bool f[2010];
int main() {
	cin>>n>>m;
	int x,y,z;
	for(int i = 1; i <= m; i++) {
		cin>>x>>y>>z;
		a[x][y] = z;
		a[y][x] = z;
	}
	cin>>s>>e;
	//dijkstra求解
	for(int i = 1; i <= n; i++) d[i] = 0x3f3f3f3f;
	d[e] = 100;
	//反推走到每个点最少需要汇出的钱数
	for(int i = 1; i <= n; i++) {
		int mi = -1;
		for(int j = 1; j <= n; j++) {
			if(!f[j]&&(mi==-1||d[j]<d[mi])) {
				mi = j;
			}
		}
		f[mi] = true;
		//更新更短的路径
		for(int j = 1; j <= n; j++) {
			if(!f[j]&&a[mi][j]&&d[mi]/(1-a[mi][j]*0.01)<d[j]) {
				d[j] = d[mi] / (1 - a[mi][j]*0.01);
			}
		}
	}
	cout<<fixed<<setprecision(8)<<d[s];
	return 0;
}
2024/12/19 19:57
加载中...