rt,用了 Floyd+log 求最短路,好像不是精度的问题,但是只有60分。
https://www.luogu.com.cn/record/36542797
#include <cstdio>
#include <cmath>
using namespace std;
typedef long double db;
const int max_n = 200, INF = 0x3f3f3f3f;
const db EPS = 1e-14;
struct costs
{
int del;
db los;
costs(int _d = 0, db _l = 0) : del(_d), los(_l) { }
bool operator<(const costs& a) const
{
if (fabs(los - a.los) > EPS)
return los < a.los;
return del < a.del;
}
costs operator+(const costs& a) const
{
return costs(del + a.del, los + a.los);
}
};
costs g[max_n][max_n];
int main()
{
int n, s, t, ta;
db tb;
scanf("%d%d%d", &n, &s, &t);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
scanf("%d", &ta);
if (ta == -1)
g[i][j].del = INF;
else
g[i][j].del = ta;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
scanf("%Lf", &tb);
if (tb == -1)
g[i][j].los = 10 * INF;
else
g[i][j].los = -log(1 - tb);
}
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (g[i][k] + g[k][j] < g[i][j])
g[i][j] = g[i][k] + g[k][j];
printf("%d %.4Lf\n", g[s-1][t-1].del, 1 - exp(-g[s-1][t-1].los));
return 0;
}