题目链接
给一个有向图， 有边权。一个路径的密度 = 这条路上的边权和 / 这条路上边的数量。有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]); } }