调试了一中午实在是不会了
查看原帖
调试了一中午实在是不会了
874765
852810242_121楼主2023/11/12 11:59
#include"iostream"
#include"cstring"
#include"cmath"
using namespace std;
const int N = 2101;
int g[N][N];
bool st[N] = {false};
int dist[N];
int n, m;
int start,finish;
double sum = 100.0;
void  dj()
{
	for (int i = 0; i < n; i++)
	{
		int t = 0;
		for (int j = 1; j <= n; j++)
		{
			if (st[j] == false && (t == 0 || dist[j] < dist[t]))
			{
				t = j;
			}
		}
		st[t] = true;
		if (t != start )
		{
			double x;
			x = 1.0 - (0.01 * dist[t]);
			sum = sum / x;
		}
		for (int j = 1; j <= n; j++)
		{
			if (st[j] == false)
			{
				dist[j] = min(dist[j], dist[t] * g[t][j]) / dist[t];
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	memset(g, 0x3f, sizeof g);
	memset(dist, 0x3f, sizeof dist);
	for (int i = 0; i < m; i++)
	{
		int v1, v2, w;
		cin >> v1>>v2 >> w;
		g[v1][v2] = w;
		g[v2][v1] = w;
	}
	cin >> start >> finish;
	dist[start] = 1;
	dj();
	printf("%.8f", sum);
	return 0;
}
2023/11/12 11:59
加载中...