瘦了的牛牛去旅游

题目链接

题目大意

给一个有向图， 有边权。一个路径的密度 = 这条路上的边权和 / 这条路上边的数量。有q次询问 ，每次询问 给两个点，问这两个点路径上的密度最小是多少。
数据范围：点的数量n（50）边的数量m（1000）询问的数量q（1e5）

题解

我做的时候比较捞。。一直没想到dp这种东西。。一看见图就一直在想怎么建图跑个什么东西。。还是菜啊
dp[i][j][k] 表示i到j经过k个边的最小路径长度。
状态转移就很简单了，找一个中间点，然后转移。。。
肯定要先枚举k因为转移k要用到k - 1.
代码：

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){
   freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){
   freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
   return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
   a %= mod;ll ans = 1;while(b){
   if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
   bool operator()(const pii & a, const pii & b){
   return a.second > b.second;}};
int lb(int x){
   return  x & -x;}

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int maxn = 100+5;
int dis[maxn][maxn];
int dp[maxn][maxn][maxn];
double ans[maxn][maxn];
int main()
{
   
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i ++ )
	{
   
		for (int j = 1; j <= n; j ++ )
		{
   
			dis[i][j] = inf;
		}
	}
	for (int i = 1; i <= n; i ++ )
	{
   
		for (int j = 1; j <= n; j ++ )
		{
   
			for (int k = 0; k <= n; k ++ )
				dp[i][j][k] = inf;
		}
	}

	for (int i = 1;  i<= m; i ++ )
	{
   
		int x,y,v;
		scanf("%d%d%d",&x,&y,&v);
		dis[x][y] = min(dis[x][y],v);
	}
	for (int  i= 1; i <= n; i ++ )
		dp[i][i][0] = 0;
	for (int k = 1; k <= n; k ++ )
	{
   
		for (int i =1; i <= n; i ++ )  // i -> j 过k个边的最小路径长度
		{
   
			for (int j = 1; j<= n; j ++ )
			{
   
				for (int p = 1; p <= n; p ++ )
				{
   
					dp[i][j][k] = min(dp[i][j][k],dp[i][p][k - 1] + dis[p][j]);
				}
			}
		}
	}
	// for (int i = 1; i <= n; i ++ )
	// {
   
	// for (int j = 1; j <= n; j ++ )
	// {
   
	// printf("%d %d\n",i,j);
	// for(int k= 1; k <= n; k ++ )
	// {
   
	// printf("%d ",dp[i][j][k]);
	// }
	// printf("\n");
	// }
	// }
	for (int i = 1; i <= n; i ++ )
	{
   
		for (int j = 1; j <= n; j ++ )
		{
   
			if(i == j)
			{
   
				ans[i][j] = 0;
				continue;
			}
			double s = inf;
			ans[i][j] = inf;
			for (int k = 1; k <= n; k ++ )
			{
   
				if(dp[i][j][k] == inf)
					continue;
				s = min(s,1.0 * dp[i][j][k]/k);
			}
			ans[i][j] = s;
		}
	}
	int q;
	scanf("%d",&q);
	while(q -- )
	{
   
		int x,y;
		scanf("%d%d",&x,&y);
		if(ans[x][y] == inf)
			printf("OMG!\n");
		else
			printf("%.3f\n",ans[x][y]);
	}
	
}