发现实际上把每个物品提出来做最短路后，可以转化为一个在图中求 最小的 ∑w∑time ∑ w ∑ t i m e 的环 上面那东西就是个01规划搞搞就行了，然后最小环直接套floyd即可 c++代码如下：
#include<bits/stdc++.h> #define eps 1e-2 #define rep(i,x,y) for(register int i = x; i <= y; ++ i ) #define repd(i,x,y) for(register int i = x ; i >= y; -- i ) using namespace std; typedef long long ll; template<typename T>inline void read(T&x) { char c;int sign = 1; x = 0; do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c)); do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c)); x *= sign; } const int N = 101,M=1e3+80; ll dis[N][N],di[N][N],s[N][M],b[N][M],n,m,K; double d[N][N]; inline bool check(double w ) { rep(i,1,n) rep(j,1,n) d[i][j] = 1e9; rep(i,1,n) rep(j,1,n) d[i][j] = min(d[i][j],dis[i][j]*w - di[i][j] ); rep(k,1,n) rep(i,1,n) rep(j,1,n) d[i][j] = min(d[i][j],d[i][k] + d[k][j]); rep(i,1,n) if(d[i][i] < 0) return true; return false; } int main() { read(n); read(m); read(K); rep(i,1,n) rep(j,1,n) dis[i][j] = 1e9; rep(i,1,n) rep(j,1,K) read(s[i][j]),read(b[i][j]); rep(i,1,m) { int v,w,p; read(v); read(w); read(p); dis[v][w] = p; } rep(k,1,n) rep(i,1,n) rep(j,1,n) dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]); rep(i,1,n) rep(j,1,n) rep(k,1,K) if(s[i][k] != -1 && b[j][k] != -1) di[i][j] = max(di[i][j],b[j][k] - s[i][k]); double l = 0,r = 1e18,mid,ans; while(fabs(r-l) > eps) { if(check(mid = (l + r) / 2 )) l = mid,ans = mid; else r = mid; } printf("%.0lf",ans-0.5); return 0; }