c/c++语言开发共享洛谷P1730 最小密度路径(floyd)

题意

题目链接

sol

zz floyd。

很显然的一个dp方程(f[i][j][k][l])表示从(i)到(j)经过了(k)条边的最小权值

可以证明最优路径的长度一定(leqslant n)

然后一波(n^4) dp就完了

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int inf = 1e9 + 10; inline int read() {     char c = getchar(); int x = 0, f = 1;     while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();     return x * f; } int n, m; int f[51][51][1001]; int main() {     //memset(f, 0x3f, sizeof(f));     n = read(); m = read();     for(int k = 1; k <= n; k++)         for(int i = 1; i <= n; i++)             for(int j = 1; j <= n; j++)                 f[i][j][k] = inf;     for(int i = 1; i <= m; i++) {         int x = read(), y = read(), w = read();         f[x][y][1] = min(f[x][y][1], w);     }     for(int l = 2; l <= n; l++)// num of edge          for(int k = 1; k <= n; k++) // mid point              for(int i= 1; i <= n; i++) // start point                  for(int j = 1; j <= n; j++) // end point                     f[i][j][l] = min(f[i][j][l], f[i][k][l - 1] + f[k][j][1]);     int q = read();     while(q--) {         int x = read(), y = read();         double ans = 1e18;         for(int i = 1; i <= n; i++) if(f[x][y][i] != inf) ans = min(ans, (double) f[x][y][i] / i);         if(ans == 1e18) puts("omg!");         else printf("%.3lfn", ans);     }     return 0; } /* */