QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #410481 | #676. Travelling Merchant | SirPh# | 0 | 57ms | 5320kb | C++20 | 2.3kb | 2024-05-14 03:00:39 | 2024-05-14 03:00:39 |
Judging History
answer
#include<bits/stdc++.h>
// #pragma GCC optimize("trapv")
using namespace std;
const int mod=(int)1e9+7;
#define endl '\n'
#define all(arr) arr.begin(),arr.end()
#define allr(arr) arr.rbegin(),arr.rend()
#define sz size()
#define int long long
int dis[101][101];
int buysell[101][101];
int dis1[101][101];
int buy[101][1001];
int sell[101][1001];
int inf=1e18;
bool overflow(int a,int b)
{
if(a>=(inf/b))return 1;
else return 0;
}
void iforgor()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=0;i<=n;i++)for(int j=0;j<k;j++)buysell[i][j]=-1e18;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=1e18;
for(int i=1;i<=n;i++)
{
for(int j=0;j<k;j++)
{
int a,b;
cin>>a>>b;
buy[i][j]=a;
sell[i][j]=b;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++){
for(int e=0;e<k;e++)
{
if(buy[i][e]==-1||sell[j][e]==-1)continue;
buysell[i][j]=max(buysell[i][j],sell[j][e]-buy[i][e]);
}
}
}
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
dis[a][b]=c;
}
for(int kk=1;kk<=n;kk++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][kk]+dis[kk][j]);
int ans=0;
int l=1,r=2e9;
int ez=0;
while(l<=r)
{
int mid=(l+r)/2;
bool negcyc=false;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis1[i][j]=1e18;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(overflow(mid,dis[i][j])||buysell[i][j]==1e18)dis1[i][j]=1e18;
else
dis1[i][j]=mid*dis[i][j]-buysell[i][j];
}
for(int kk=1;kk<=n;kk++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis1[i][j]=min(dis1[i][j],dis1[i][kk]+dis1[kk][j]);
for(int i=1;i<=n;i++)if(dis1[i][i]<=0)negcyc=true,ez=i;
if(negcyc)
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
cout<<ans<<endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t=1;
// cin>>t;
while(t--)iforgor();
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 38ms
memory: 5268kb
input:
100 181 1000 553730496 158361961 892706912 178296397 743382683 297380306 641674485 99624440 917350062 18856036 844421978 187895310 648680590 312745394 560991872 402321479 712754581 166489560 776432653 57402415 554268728 511597509 861517186 541462029 843246768 457630601 923371196 521104850 557772066 ...
output:
0
result:
wrong answer 1st lines differ - expected: '1', found: '0'
Subtask #2:
score: 0
Wrong Answer
Test #14:
score: 21
Accepted
time: 4ms
memory: 4100kb
input:
50 50 20 1000000000 94476 1000000000 75837 1000000000 27079 1000000000 129004 1000000000 100830 1000000000 98560 1000000000 99302 1000000000 65993 30410 1 1000000000 66183 1000000000 89148 1000000000 21236 1000000000 11935 1000000000 53895 1000000000 126490 1000000000 104741 1000000000 78615 1000000...
output:
1003
result:
ok single line: '1003'
Test #15:
score: 21
Accepted
time: 4ms
memory: 4164kb
input:
50 50 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 339508586 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
output:
15782746
result:
ok single line: '15782746'
Test #16:
score: 21
Accepted
time: 4ms
memory: 4100kb
input:
50 50 50 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10000 10000 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
output:
203
result:
ok single line: '203'
Test #17:
score: 21
Accepted
time: 4ms
memory: 4112kb
input:
48 48 50 -1 -1 10002 10002 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
output:
212
result:
ok single line: '212'
Test #18:
score: 0
Wrong Answer
time: 4ms
memory: 4080kb
input:
50 50 50 662985743 94901609 899384837 65628166 673532122 180059305 627752310 127592351 824072744 87540640 507122543 377977048 635262419 187630987 838541684 187757801 577199874 274873255 694303855 184204318 853356130 175381182 520003147 69588361 734732717 178931356 807461406 173458145 548944353 44467...
output:
22815785
result:
wrong answer 1st lines differ - expected: '24700682', found: '22815785'
Subtask #3:
score: 0
Wrong Answer
Test #37:
score: 33
Accepted
time: 57ms
memory: 5320kb
input:
100 243 1000 969713863 380451398 977287381 546839551 578242281 267067963 834635238 316438277 806980243 189648353 779415475 453867771 741678190 352485450 473763928 190177433 687118672 377243148 644333594 197290749 949048287 436673078 690006797 180711316 714366028 387342721 980055654 198167471 8873988...
output:
28
result:
ok single line: '28'
Test #38:
score: 0
Wrong Answer
time: 0ms
memory: 3644kb
input:
5 7 4 727218133 319808016 451811473 341827334 983666612 208956608 712124347 20325770 625539547 511168571 950094471 396282690 649119245 412489786 504515934 498965733 955685647 120970424 900386157 487638774 666900039 254430876 841869836 23162184 670731166 282497058 791738936 425566820 916482877 602671...
output:
0
result:
wrong answer 1st lines differ - expected: '8', found: '0'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%