1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
| #include <bits/extc++.h> #include <bits/stdc++.h> #pragma gcc optimize("ofast,unroll-loops,no-stack-protector,fast-math") #pragma gcc target("abm,bmi,bmi2,mmx,sse,sse2,sse3,ssse3,sse4,popcnt,avx,avx2,fma,tune=native") #pragma comment(linker, "/stack:200000000") #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define int long long #define double long double #define pb push_back #define sz(x) (int)(x).size() #define all(v) begin(v),end(v) #define debug(x) cerr<<#x<<" = "<<x<<'\n' #define LINE cout<<"\n-----------------\n" #define endl '\n' #define VI vector<int> #define F first #define S second #define MP(a,b) make_pair(a,b) #define rep(i,m,n) for(int i = m;i<=n;++i) #define res(i,m,n) for(int i = m;i>=n;--i) #define gcd(a,b) __gcd(a,b) #define lcm(a,b) a*b/gcd(a,b) #define Case() int _;cin>>_;for(int Case = 1;Case<=_;++Case) #define pii pair<int,int> using namespace __gnu_cxx; using namespace __gnu_pbds; using namespace std; template <typename K, typename cmp = less<K>, typename T = thin_heap_tag> using _heap = __gnu_pbds::priority_queue<K, cmp, T>; template <typename K, typename M = null_type> using _hash = gp_hash_table<K, M>; template <typename K, typename M = null_type, typename cmp = less<K>, typename T = rb_tree_tag> using _tree = tree<K, M, cmp, T, tree_order_statistics_node_update>; template <typename K, typename M = null_type, typename cmp = less_equal<K>, typename T = rb_tree_tag> using _multitree = tree<K, M, cmp, T, tree_order_statistics_node_update>; const int N = 1e6+5,L = 20,mod = 1e9+7,inf = 1e9+7; const double eps = 1e-7;
void floyd(vector<vector<int>>&dp,int n){ for(int k = 1;k<=n;++k){ for(int i = 1;i<=n;++i){ for(int j = 1;j<=n;++j){ dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]); } } } } void solve(){ int n,m,k; cin>>n>>m>>k; vector<vector<int>>t(105,vector<int>(105,inf)),s(105,vector<int>(105)); vector<vector<pii>>v(n+5,vector<pii>(k)); for(int i = 1;i<=n;++i){ for(int j = 0;j<k;++j){ cin>>v[i][j].F>>v[i][j].S; } } for(int i = 0;i<m;++i){ int a,b; cin>>a>>b>>t[a][b]; } floyd(t,n); for(int i = 1;i<=n;++i){ for(int j = 1;j<=n;++j){ if(t[i][j]==inf)continue; for(int l = 0;l<k;++l){ if(v[i][l].F==-1 or v[j][l].S==-1)continue; s[i][j] = max(s[i][j],v[j][l].S-v[i][l].F); } } } function<bool(int)>check = [&](int x){ vector<vector<int>>dp(n+5,vector<int>(n+5,inf)); for(int i = 1;i<=n;++i){ for(int j = 1;j<=n;++j){ dp[i][j] = -(s[i][j]-x*t[i][j]); } } floyd(dp,n); for(int i = 1;i<=n;++i){ if(dp[i][i]<=0)return 1; } return 0; }; int l = 0,r = inf,ans = 0; while(l<=r){ int m = (l+r)>>1; if(check(m)){ ans = m; l = m+1; } else{ r = m-1; } } cout<<ans<<endl; } signed main(){ IOS; solve(); }
|