NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #184626 | #2058. 小游戏 | gispzjz | 100 | 1359ms | 32284kb | C++ | 1.2kb | 2023-09-09 14:12:11 | 2023-09-09 14:12:13 |
answer
#include <cstdio>
#include <algorithm>
using namespace std;
int edge[500000],next[500000],dist[500000],first[200000];
int b[200000],d[200000],g[10000000],h[10000000],p[200000],r[200000];
int i,k,m,n,x,y,z,head,tail,sum_edge;
int main()
{
//freopen("excitement.in","r",stdin);
//freopen("excitement.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for (i=1;i<=n;i++)
scanf("%d",&r[i]);
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
sum_edge++,edge[sum_edge]=y,next[sum_edge]=first[x],dist[sum_edge]=z,first[x]=sum_edge;
sum_edge++,edge[sum_edge]=x,next[sum_edge]=first[y],dist[sum_edge]=z,first[y]=sum_edge;
}
d[1]=p[1]=k;
tail++,g[tail]=1,h[tail]=0;
for (head=1;head<=tail;head++)
{
if (g[head]==n)
{
printf("%d\n",h[head]);
return 0;
}
if (h[head]!=h[head-1])
for (i=head;i<=tail;i++)
d[g[i]]=p[g[i]],b[g[i]]=0;
for (i=first[g[head]];i!=0;i=next[i])
if ((d[g[head]]>dist[i]) && (min(d[g[head]]-dist[i]+r[edge[i]],k)>p[edge[i]]))
{
p[edge[i]]=min(d[g[head]]-dist[i]+r[edge[i]],k);
if (! b[edge[i]])
tail++,g[tail]=edge[i],h[tail]=h[head]+1,b[edge[i]]=1;
}
}
printf("-1\n");
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 544kb
input:
5 10 10 3 3 0 1 1 4 4 1 4 3 1 3 2 6 3 4 10 5 1 5 1 3 9 2 5 19 2 5 1 5 2 10 2 1 4
output:
1
result:
ok single line: '1'
Test #2:
score: 10
Accepted
time: 0ms
memory: 532kb
input:
5 10 10 1 0 1 3 0 5 2 1 5 2 8 4 3 18 1 3 10 5 3 5 2 3 8 5 3 15 3 1 11 4 5 9 2 4 1
output:
-1
result:
ok single line: '-1'
Test #3:
score: 10
Accepted
time: 0ms
memory: 544kb
input:
5 10 10 0 3 1 1 1 1 3 12 5 4 8 1 1 6 5 2 1 2 5 3 1 4 2 1 4 4 4 5 5 4 2 9 3 4 2
output:
2
result:
ok single line: '2'
Test #4:
score: 10
Accepted
time: 0ms
memory: 548kb
input:
20 50 20 4 0 3 4 3 0 5 2 5 0 5 2 5 2 0 6 2 3 4 2 16 5 18 9 1 24 14 16 27 5 16 32 14 7 31 13 20 23 6 ...
output:
10
result:
ok single line: '10'
Test #5:
score: 10
Accepted
time: 0ms
memory: 564kb
input:
100 500 20 2 5 5 3 0 1 1 3 4 2 5 5 5 4 5 3 1 0 2 5 5 5 2 2 1 4 0 1 6 0 1 5 2 4 5 4 4 6 3 0 0 1 5 1 3...
output:
11
result:
ok single line: '11'
Test #6:
score: 10
Accepted
time: 0ms
memory: 584kb
input:
500 1000 500 143 113 118 133 51 100 155 76 81 43 8 91 85 65 61 69 1 30 135 125 0 43 126 20 40 52 165...
output:
11
result:
ok single line: '11'
Test #7:
score: 10
Accepted
time: 0ms
memory: 720kb
input:
1000 5000 1000 94 154 195 48 124 134 103 168 192 122 101 8 5 197 62 123 36 129 90 48 24 43 104 7 108...
output:
32
result:
ok single line: '32'
Test #8:
score: 10
Accepted
time: 41ms
memory: 3076kb
input:
10000 50000 10000 30 96 44 6 84 58 47 34 35 80 49 45 47 76 93 16 2 83 23 79 81 12 66 81 96 3 37 4 69...
output:
39
result:
ok single line: '39'
Test #9:
score: 10
Accepted
time: 627ms
memory: 29736kb
input:
30000 100000 20000 21 95 28 93 22 5 16 70 27 36 38 21 7 11 8 46 88 19 98 80 70 53 73 83 79 93 55 75 ...
output:
1726
result:
ok single line: '1726'
Test #10:
score: 10
Accepted
time: 691ms
memory: 32284kb
input:
30000 100000 20000 94 72 1 42 14 15 63 14 26 25 44 9 1 71 75 85 98 80 87 49 10 47 73 16 98 13 62 72 ...
output:
1594
result:
ok single line: '1594'
