# [洛谷春令营 D7T3] 最小密度路径【分步Floyd】

• 2018-02-21
• 0
• 0

## Problem:

```3 3
1 3 5
2 1 6
2 3 6
2
1 3
2 3
```

```5.000
5.500
```

### 说明

1 ≤ N ≤ 50，1 ≤ M ≤ 1000，1 ≤ W ≤ 100000，1 ≤ Q ≤ 100000

## Code: O(N4) [2753K, 56MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define DINF 1e10
using namespace std;

inline void getint(int &num){
char ch;
while(!isdigit(ch = getchar()));
num = ch - '0';
while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int N, M, dis[52][52][52], Q;
double minden[52][52];

int main(){
getint(N), getint(M);
memset(dis, 0x3f, sizeof(dis));
for(register int i = 1; i <= M; i++){
int A, B, W;
getint(A), getint(B), getint(W);
if(W < dis[1][A][B]) dis[1][A][B] = W;
}
for(register int stp = 2; stp < N; stp++)
for(register int k = 1; k <= N; k++)
for(register int i = 1; i <= N; i++)
for(register int j = 1; j <= N; j++)
dis[stp][i][j] = min(dis[stp][i][j], dis[stp - 1][i][k] + dis[1][k][j]);  // 分步 Floyd 算法
memset(minden, 0x43, sizeof(minden));  // memset 为 double 赋极大值
for(register int i = 1; i <= N; i++)
for(register int j = 1; j <= N; j++)
for(register int stp = 1; stp < N; stp++)
if(dis[stp][i][j] < INF)
minden[i][j] = min(minden[i][j], (double)dis[stp][i][j] / stp);
getint(Q);
while(Q--){
int X, Y;
getint(X), getint(Y);
if(minden[X][Y] < DINF) printf("%.3f\n", minden[X][Y]);
else puts("OMG!");
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai