Solution
这题的话。。首先答案的形式应该是\(01\)分数规划了
然后比较关键的一步在于，我们需要简化一下交易的过程
具体一点就是，我们将中间经过的不交易的点和路径全部”合并“起来，只考虑买入物品和卖出物品的两个点
首先看一下这两个点之间的路程应该怎么走
因为路程长度是做分母的那个，所以我们肯定希望在到达同一个点的情况下走最短路，那所以这两个点一旦确定下来了，路程也就确定下来了
两两之间最短路的求解因为\(N\)比较小所以可以直接用floyd解决
然后接下来就是交易的物品我们要选择哪一个
很明显是选盈利最大的那个，大力贪心就好了ovo
所以总的来说，如果确定了进行买卖的两个点，我们走的路程一定是最短路，买卖的一定是这两个点能够交易的所有物品中，盈利最大的那个
记两点间最短路为\(w_{i,j}\)，最优的盈利为\(val_{i,j}\)，那么套用分数规划的套路（Portal -->【learning】），我们需要快速求出一个环的：
\[max(\sum val_{i,j}-\lambda' \sum w_{i,j})
\]
\]
与\(0\)的大小关系
那么这个其实就直接用spfa判断是否有正环就好了
自己跳进去的坑：
额。。注意到这里题目说的是**利润/路径长度（向下取整） **的最大值。。
所以！在二分答案的时候！\(l\)和\(r\)和\(mid\)用int就好了！！ QWQ
以及\(K\)的范围是\(1000\)而不是\(100\)。。。
代码大概长这个样子
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=110,M=9910,inf=2147483647;
const double eps=1e-8;
struct xxx{
int y,x,nxt;
double w;
}a[N*N*2];
struct Data{
int y,x;
int w;
}rec[N*N*2];
queue<int> q;
int h[N],cnt[N],buy[N][1010],sell[N][1010],w[N][N];
double val[N];
bool vis[N];
int n,m,K,tot,rec_cnt;
void add(int x,int y,double val);
bool spfa();
void build(double mid);
bool check(double mid);
void prework();
void floyd();
void solve();
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
#endif
scanf("%d%d%d",&n,&m,&K);
for (int i=1;i<=n;++i)
for (int j=1;j<=K;++j)
scanf("%d%d",&buy[i][j],&sell[i][j]);
int x,y,w1;
rec_cnt=0;
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
w[i][j]=inf;
for (int i=1;i<=m;++i){
scanf("%d%d%d",&x,&y,&w1);
rec[++rec_cnt].x=x; rec[rec_cnt].y=y; rec[rec_cnt].w=0;
w[x][y]=min(w[x][y],w1);
}
prework();
solve();
}
void add(int x,int y,double val){
//printf("%d %d %.3lf\n",x,y,val);
a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot; a[tot].w=val;
}
bool spfa(){
while (!q.empty()) q.pop();
int u,v;
for (int i=1;i<=n;++i) vis[i]=true,q.push(i),cnt[i]=0,val[i]=0;
while (!q.empty()){
v=q.front(); q.pop();
for (int i=h[v];i!=-1;i=a[i].nxt){
u=a[i].y;
if (val[u]<=val[v]+a[i].w){
val[u]=val[v]+a[i].w;
if (!vis[u]){
q.push(u),vis[u]=true,++cnt[u];
if (cnt[u]>n) return true;
}
}
}
vis[v]=false;
}
return false;
}
bool check(double mid){
build(mid);
return spfa();
}
void build(double mid){
tot=0;
for (int i=1;i<=n;++i) h[i]=-1;
for (int i=1;i<=rec_cnt;++i)
add(rec[i].x,rec[i].y,1.0*rec[i].w-mid*w[rec[i].x][rec[i].y]);
}
void floyd(){
for (int k=1;k<=n;++k)
for (int i=1;i<=n;++i){
if (w[i][k]==inf) continue;
for (int j=1;j<=n;++j)
if (w[k][j]!=inf)
w[i][j]=min(w[i][j],w[i][k]+w[k][j]);
}
}
void prework(){
floyd();
int mx,tmp;
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j){
if (w[i][j]==inf) continue;
mx=0;
for (int k=1;k<=K;++k)
if (buy[i][k]!=-1&&sell[j][k]!=-1){
if (sell[j][k]-buy[i][k]>mx) tmp=k;
mx=max(mx,sell[j][k]-buy[i][k]);
}
if (mx)
rec[++rec_cnt].x=i,rec[rec_cnt].y=j,rec[rec_cnt].w=mx;
}
}
void solve(){
int l=0,r=1e9,mid,ans;
while (l<=r){
mid=(l+r)>>1;
if (check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d\n",ans);
}