NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #213435 | #2058. 小游戏 | ZzhAllen | 0 | 65ms | 29388kb | C++11 | 1.3kb | 2024-11-11 22:39:52 | 2024-11-11 23:11:27 |
answer
#include <bits/stdc++.h>
using namespace std;
#define F(i,x,y) for (int i = x; i <= y; i ++ )
#define D(i,x,y) for (int i = x; i >= y; i -- )
#define E(i,u) for (auto &i : u)
#define u first
#define v second
#define pii pair<int,int>
const int N = 3e4 + 10, M = 1e5 + 10;
#define int long long
int n, m, hpM, a[N];
vector<pii> G[N];
bool flag = false;
bool vis[N];
void dfs(int now, int hp, int depth, int maxD)
{
if (depth > maxD) return;
if (flag) return;
if (now == n)
return flag = true, void();
hp = min(hpM,hp + a[now]);
// vis[now] = 1;
E(t, G[now])
{
auto u = t.u, w = t.v;
// if (vis[u]) continue;
if (hp - w < 0) continue;
if (maxD == 10)
cout << now << "->" << u << '\n';
dfs(u, hp - w, depth + 1, maxD);
if (flag) return;
}
}
void koishi()
{
cin >> n >> m >> hpM;
F(i,1,n) cin >> a[i];
F(i,1,m)
{
int u, v, w;
cin >> u >> v >> w;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
int l = m - 1, r = m*(m - 1)/2 + 1, mid = 0;
while (l + 1 < r)
{
mid = (l + r) >> 1;
dfs(1, hpM, 0, mid);
if (flag) r = mid;
else l = mid;
flag = false;
// memset(vis, 0, sizeof vis);
}
cout << l;
}
#undef int
int main()
{
cin.tie(nullptr) -> sync_with_stdio(false);
koishi();
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 1960kb
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->5 9
result:
wrong answer 1st lines differ - expected: '1', found: '1->5'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 1960kb
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:
45
result:
wrong answer 1st lines differ - expected: '-1', found: '45'
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 1956kb
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:
1->1 1->4 4->1 4->3 3->4 1->4 1->1 1->4 4->1 4->3 3->4 1->4 1->4 4->5 9
result:
wrong answer 1st lines differ - expected: '2', found: '1->1'
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 2024kb
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:
49
result:
wrong answer 1st lines differ - expected: '10', found: '49'
Test #5:
score: 0
Wrong Answer
time: 4ms
memory: 8836kb
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:
499
result:
wrong answer 1st lines differ - expected: '11', found: '499'
Test #6:
score: 0
Wrong Answer
time: 60ms
memory: 29388kb
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:
999
result:
wrong answer 1st lines differ - expected: '11', found: '999'
Test #7:
score: 0
Memory Limit Exceeded
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:
result:
Test #8:
score: 0
Memory Limit Exceeded
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:
result:
Test #9:
score: 0
Memory Limit Exceeded
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:
result:
Test #10:
score: 0
Time Limit Exceeded
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 ...
