QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#360170#6523. Escape PlanDjangle162857WA 734ms99784kbC++201.6kb2024-03-21 14:11:192024-03-21 14:11:20

Judging History

你现在查看的是最新测评结果

  • [2024-03-21 14:11:20]
  • 评测
  • 测评结果:WA
  • 用时:734ms
  • 内存:99784kb
  • [2024-03-21 14:11:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3fll;
const int N = 1000005;
int t, n, m, k;
struct Edge {
	int v, w;
	bool operator<(const Edge &rsh) const
	{
		return w > rsh.w;
	}
};
vector<Edge> g[N];
int dp[N], d[N], e[N];
priority_queue<Edge> q;
priority_queue<int> mn[N];	//求解第d[i]+1小的数,用一个大根堆
signed main()
{
	// cout << "ok" << endl;
	cin >> t;
	while (t--) {
		cin >> n >> m >> k;

		//初始化
		while (q.size())
			q.pop();
		for (int i = 1; i <= n; i++)
			dp[i] = inf;
		for (int i = 1; i <= n; i++)
			g[i].clear();
		for (int i = 1; i <= n; i++)
			while (mn[i].size())
				mn[i].pop();
		for (int i = 1; i <= n; i++)
			dp[i] = inf;

		for (int i = 1; i <= k; i++) {
			scanf("%lld", &e[i]);
			q.push((Edge){e[i], 0});
		}
		for (int i = 1; i <= n; i++) {
			scanf("%lld", &d[i]);
			d[i]++;
		}
		for (int i = 1; i <= m; i++) {
			int u, v, w;
			scanf("%lld%lld%lld", &u, &v, &w);
			g[u].push_back((Edge){v, w});
			g[v].push_back((Edge){u, w});
		}
		while (q.size()) {
			int v = q.top().v, _dp = q.top().w;
			q.pop();
			if (dp[v] < inf)
				continue;
			dp[v] = _dp;

			for (int i = 0; i < g[v].size(); i++) {
				int u = g[v][i].v, w = g[v][i].w;
				if (dp[u] < inf)
					continue;
				// cout<<"1"<<endl;
				if (mn[u].size() < d[u])
					mn[u].push(w + _dp);
				if (mn[u].size() == d[u])
					q.push((Edge){u, mn[u].top()});
			}
		}
		if (dp[1] < inf)
			cout << dp[1] << endl;
		else
			cout << -1 << endl;
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 35036kb

input:

2
3 4 1
3
1 1 1
1 2 1
1 2 2
2 3 1
2 3 2
3 2 2
2 3
2 0 0
1 2 1
1 3 1

output:

4
-1

result:

ok 2 number(s): "4 -1"

Test #2:

score: -100
Wrong Answer
time: 734ms
memory: 99784kb

input:

100
100 1808 2
94 47
3 3 0 2 4 3 3 4 0 0 2 2 2 3 2 4 0 2 3 4 4 2 0 3 4 3 1 0 2 1 2 2 0 3 4 4 4 1 2 2 3 1 0 0 3 1 4 2 1 3 3 4 3 0 4 1 0 3 2 1 4 4 1 3 2 3 3 3 3 1 0 3 0 4 3 1 0 4 0 4 4 1 2 0 0 4 1 3 3 3 0 2 2 1 1 2 3 4 1 2
72 29 1138
59 78 2398
95 5 1610
32 46 4176
36 99 8143
100 69 413
61 58 1595
9 9...

output:

8619
1021
9557
7664
5555
7413
8935
7487
9433
9832
11262
9597
9165
12162
9820
12363
11265
9812
10989
4923
13199
12942
8185
10757
14101
17965
10003
2322
5387
9734
10780
11427
4157
-1
10207
6265
7250
8948
10626
10529
4253
9173
21843
10625
9100
11884
-1
986
4335
11773
-1
3166
7387
13886
13998
5770
11188...

result:

wrong answer 1st numbers differ - expected: '5109', found: '8619'