NOI.AC
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #194341 | #3416. 上课计划 | sunchenyu2012 | 100 | 1054ms | 2484kb | C++ | 1.2kb | 2023-10-15 10:59:35 | 2023-10-15 12:30:07 |
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 405
using namespace std;
int dp[N][N],v[N][N],n,m,q,t,s;
struct node{
int a,b,p;
}e[N];
bool cmp(node x,node y){
return x.a<y.a;
}int main(){
scanf("%d%d%d%d%d",&n,&m,&q,&t,&s);
e[0]=(node){0,0,1};
for(int i=1;i<=n;i++)for(int j=2;j<=n;j++)dp[j][i]=dp[i][j]=1000000000;
for(int i=1;i<=n;i++)dp[i][i]=0;
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
dp[b][a]=dp[a][b]=c;
}for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
dp[i][j]=dp[j][i]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}for(int i=1;i<=q;i++)scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].p);
sort(e+1,e+q+1,cmp);
for(int i=0;i<=q+1;i++)for(int j=0;j<=q;j++)v[i][j]=-1000000000;
v[0][0]=0;
for(int i=1;i<=q;i++){
for(int j=0;j<i;j++){
if(dp[e[i].p][e[j].p]>e[i].a-e[j].b)continue;
for(int z=q;z>=1;z--){
v[i][z]=max(v[i][z],v[j][z-1]+max(0,e[i].a-e[j].b-dp[e[i].p][1]-dp[1][e[j].p]));
}
}
}int ma=0;
for(int j=0;j<=q;j++){
if(dp[1][e[j].p]>t-e[j].b)continue;
for(int z=q;z>=0;z--){
v[q+1][z]=max(v[q+1][z],v[j][z]+max(0,t-e[j].b-dp[1][e[j].p]));
}
}for(int i=1;i<=q;i++)ma=v[q+1][i]>=s?i:ma;
printf("%d",ma);
return 0;
}
Details
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1276kb
input:
20 77 20 20 10 1 12 1 4 6 1 1 16 1 12 6 1 5 12 1 4 17 1 5 3 1 7 4 1 11 20 1 1 10 1 8 16 1 15 1 1 16 ...
output:
5
result:
ok single line: '5'
Test #2:
score: 10
Accepted
time: 1ms
memory: 1272kb
input:
20 64 20 20 9 15 14 1 2 20 1 5 16 1 13 16 1 7 13 1 11 16 1 18 7 1 14 2 1 1 18 1 4 2 1 19 3 1 14 18 1...
output:
4
result:
ok single line: '4'
Test #3:
score: 10
Accepted
time: 1ms
memory: 1280kb
input:
20 80 20 20 0 7 13 1 6 1 1 20 6 1 2 13 1 18 8 1 6 10 1 14 6 1 4 6 1 1 14 1 17 13 1 6 17 1 6 18 1 12 ...
output:
7
result:
ok single line: '7'
Test #4:
score: 10
Accepted
time: 2ms
memory: 1528kb
input:
100 1565 100 100 10 22 46 9 2 19 17 87 68 31 32 7 88 72 35 92 72 18 7 70 79 90 93 7 76 81 52 15 51 1...
output:
9
result:
ok single line: '9'
Test #5:
score: 10
Accepted
time: 2ms
memory: 1532kb
input:
100 1534 100 100 9 79 42 98 91 93 14 15 73 79 81 97 77 73 8 98 96 78 10 46 27 93 5 89 20 42 83 31 50...
output:
7
result:
ok single line: '7'
Test #6:
score: 10
Accepted
time: 5ms
memory: 1532kb
input:
100 1483 100 100 0 31 61 98 89 2 43 89 52 1 17 96 93 33 74 72 20 69 41 67 79 10 63 8 20 76 4 49 2 41...
output:
10
result:
ok single line: '10'
Test #7:
score: 10
Accepted
time: 266ms
memory: 2484kb
input:
400 24256 400 9999 2222 282 354 7562 183 32 1619 182 67 7578 64 390 3207 232 323 4857 144 66 6150 16...
output:
29
result:
ok single line: '29'
Test #8:
score: 10
Accepted
time: 317ms
memory: 2480kb
input:
400 24062 400 9999 1111 57 29 957 193 399 970 285 394 172 192 100 541 373 12 402 191 212 909 219 320...
output:
136
result:
ok single line: '136'
Test #9:
score: 10
Accepted
time: 324ms
memory: 2484kb
input:
400 79800 400 100000000 1111111 207 253 10000 339 207 10000 270 150 10000 227 171 10000 51 390 10000...
output:
32
result:
ok single line: '32'
Test #10:
score: 10
Accepted
time: 136ms
memory: 2484kb
input:
400 79800 400 100000000 1111111 45 128 10000 370 16 10000 235 224 10000 359 338 10000 384 117 10000 ...
output:
31
result:
ok single line: '31'
Extra Test:
score: 0
Extra Test Passed
