NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #184974 | #2058. 小游戏 | yyh_yyds | 100 | 1753ms | 5308kb | C++11 | 941b | 2023-09-17 16:59:29 | 2023-09-17 16:59:30 |
answer
#include<bits/stdc++.h>
#define fir first
#define sed second
using namespace std;
typedef pair<int,int> PII;
const int N=3e4+10,M=1e5+10;
int n,m,W;
vector<PII> g[N];
int w[N],dist[N];
struct node
{
int pt,val,ti;
};
int main()
{
scanf("%d %d %d",&n,&m,&W);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<=m;i++)
{
int xx,yy,zz;
scanf("%d %d %d",&xx,&yy,&zz);
g[xx].push_back(make_pair(yy,zz));
g[yy].push_back(make_pair(xx,zz));
}
queue<node > q;
q.push({1,W,0});
while(!q.empty())
{
auto t=q.front();
q.pop();
int u=t.pt;
int val=t.val;
int ti=t.ti;
for(int i=0;i<g[u].size();i++)
{
if(g[u][i].sed<val)
{
int j=g[u][i].fir;
int v=min(W,w[j]+val-g[u][i].sed);
if(v>dist[j])
{
dist[j]=v;
q.push({j,v,ti+1});
if(j==n){
printf("%d\n",ti+1);
return 0;
}
}
}
}
}
puts("-1");
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 1ms
memory: 1948kb
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: 1932kb
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: 1948kb
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: 1944kb
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: 1964kb
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: 1ms
memory: 1988kb
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: 3ms
memory: 2096kb
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: 56ms
memory: 3756kb
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: 942ms
memory: 5308kb
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: 750ms
memory: 5192kb
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'
