QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #672166 | #6772. Spicy Restaurant | ACAAA# | TL | 1ms | 5644kb | C++23 | 1.2kb | 2024-10-24 15:54:40 | 2024-10-24 15:55:24 |
Judging History
answer
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 5e5 + 10,M=1e5+10;
typedef pair<int, int>pii;
int n, m, k, w[M],ans[N],minn=1000;
vector<int>a[M];
pii p[N];
struct State {
int who,pos,dis;
};
void bfs() {
for (int i = 1; i <= k; i++)
ans[i] = 1e9;
queue<State>q;
for (int i = 1; i <= k; i++) {
if (minn > p[i].second)
ans[i] = -1;
else
q.push({ i,p[i].first,0 });
}
while (!q.empty()) {
State s = q.front();
q.pop();
if (ans[s.who] != 1e9)
continue;
if (p[s.who].second >= w[s.pos])
ans[s.who] = s.dis;
for (int i = 0; i < a[s.pos].size(); i++) {
int v = a[s.pos][i];
q.push({ s.who,v,s.dis + 1 });
}
}
}
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> w[i];
minn = min(minn, w[i]);
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
for (int i = 1; i <= k; i++) {
int pos, w;
cin >> pos >> w;
p[i] = { pos,w };
}
bfs();
for (int i = 1; i <= k; i++) {
cout << ans[i] << "\n";
}
}
/*
4 4 5
5 4 2 3
1 2
2 3
3 4
4 1
1 1
1 2
1 3
1 4
1 5
- 1
2
1
1
0
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5644kb
input:
4 4 5 5 4 2 3 1 2 2 3 3 4 4 1 1 1 1 2 1 3 1 4 1 5
output:
-1 2 1 1 0
result:
ok 5 lines
Test #2:
score: -100
Time Limit Exceeded
input:
50000 100000 100000 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...