QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#294852#5458. Shortest Path Queryushg8877WA 108ms14268kbC++141.4kb2023-12-30 16:59:052023-12-30 16:59:06

Judging History

你现在查看的是测评时间为 2023-12-30 16:59:06 的历史记录

  • [2024-06-21 12:38:56]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:144ms
  • 内存:14380kb
  • [2023-12-30 16:59:06]
  • 评测
  • 测评结果:0
  • 用时:108ms
  • 内存:14268kb
  • [2023-12-30 16:59:05]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=5e4+5;
int n,m,q;
struct Point{
	int x,y;
	Point(int _x=0,int _y=0){x=_x,y=_y;} 
};
Point operator -(Point x,Point y){return (Point){x.x-y.x,x.y-y.y};} 
ll operator *(Point x,Point y){return x.x*y.y-x.y*y.x;} 
vector<Point> conh[MAXN];
vector<pair<int,int> > edg[MAXN];
vector<Point> solve(vector<Point> p){
	static Point st[MAXN]; static int top;
	top=0;
	sort(p.begin(),p.end(),[&](Point x,Point y){return atan2(x.x,x.y)>atan2(y.x,y.y);});
	for(Point q:p){
		while(top>=2&&(q-st[top])*(q-st[top-1])>=0) top--;
		st[++top]=q;
	}
	p.clear();
	for(int i=1;i<=top;i++) p.push_back(st[i]);
	return p;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	conh[1].push_back(Point(0,0));
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		edg[v].push_back(MP(u,w));
	}
	for(int i=2;i<=n;i++){
		vector<Point> nds;
		for(auto e:edg[i]) for(auto p:conh[e.first])
			nds.push_back(Point(p.x+(e.second==1),p.y+(e.second==0)));
		conh[i]=solve(nds);
	}
	cin>>q;
	while(q--){
		int a,b,x;cin>>b>>a>>x;
		int ans=1e9;
		auto cal=[&](int id){
			auto p=conh[x][id];
			int r=a*p.x+b*p.y;
			ans=min(ans,r);
			return r; 
		};
		for(int i=0;i<conh[x].size();i++) cal(i);
		cout<<ans<<endl;
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 6380kb

input:

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

output:

3
4
4

result:

ok 3 number(s): "3 4 4"

Test #2:

score: -100
Wrong Answer
time: 108ms
memory: 14268kb

input:

50000 100000
1 2 1
2 3 0
3 4 1
4 5 0
5 6 1
6 7 0
7 8 1
8 9 1
9 10 0
10 11 1
11 12 1
12 13 1
13 14 0
14 15 0
15 16 0
16 17 0
17 18 1
18 19 1
19 20 0
20 21 1
21 22 0
22 23 0
23 24 1
24 25 1
25 26 0
26 27 1
27 28 0
28 29 0
29 30 0
30 31 0
31 32 1
32 33 0
33 34 1
34 35 1
35 36 1
36 37 1
37 38 0
38 39 0
...

output:

194826300
240573628
268778434
296599514
101215280
17433588
52651028
65842124
47441376
277065662
96151412
95582418
302923294
196921966
242206932
155982714
116885900
84052424
202775300
79665902
90237270
232679612
215325552
224093234
335907280
194160862
198769788
109346944
101775854
321335662
178859316...

result:

wrong answer 1st numbers differ - expected: '164602050', found: '194826300'