NO IMAGE

題目描述


給出一張有N個點M條邊的加權有向無環圖,接下來有Q個詢問,每個詢問包括2個節點X和Y,要求算出從X到Y的一條路徑,使得密度最小(密度的定義為,路徑上邊的權值和除以邊的數量)。

輸入格式:


第一行包括2個整數N和M。

以下M行,每行三個數字A、B、W,表示從A到B有一條權值為W的有向邊。

再下一行有一個整數Q。

以下Q行,每行一個詢問X和Y,如題意所訴。

輸出格式:


對於每個詢問輸出一行,表示該詢問的最小密度路徑的密度(保留3位小數),如果不存在這麼一條路徑輸出“OMG!”(不含引號)。

說明


1 ≤ N ≤ 10,1 ≤ M ≤ 100,1 ≤ W ≤ 1000,1 ≤ Q ≤ 1000

Analysis


想著是跟葫蘆一樣的最優比例路徑然而是暴力
f[i][j][k]f[i][j][k] 表示從ii走到jj過kk條邊的最短路
詢問的時候列舉一下走過幾條邊就可以了

Code


#include <cstdio>
#include <cstring>
#define INF 0x3f3f3f3f
#define N 111
#define M 1111
using namespace std;
int f[N][N][M];
int main()
{
for (int i=0;i<N;i  )
for (int j=0;j<N;j  )
for (int k=0;k<M;k  )
f[i][j][k]=INF;
int n,m;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i  )
{
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
if (w<f[x][y][1])
f[x][y][1]=w;
}
for (int l=2;l<=n;l  )
for (int k=1;k<=n;k  )
for (int i=1;i<=n;i  )
for (int j=1;j<=n;j  )
if (i!=j&&j!=k&&i!=k&&f[i][j][l]>f[i][k][l-1] f[k][j][1])
f[i][j][l]=f[i][k][l-1] f[k][j][1];
int q;
scanf("%d",&q);
while (q--)
{
int x,y;
scanf("%d%d",&x,&y);
double ans=INF;
for (int i=1;i<=m;i  )
if (f[x][y][i]<INF&&f[x][y][i]/(i*1.0)<ans)
ans=f[x][y][i]/(i*1.0);
if (ans<INF)
printf("%.3f\n",ans);
else
printf("OMG!\n");
}
return 0;
}