QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#294841#5458. Shortest Path Queryushg8877WA 0ms6444kbC++141.4kb2023-12-30 16:55:512023-12-30 16:55:52

Judging History

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

  • [2024-06-21 12:38:54]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:1ms
  • 内存:6460kb
  • [2023-12-30 16:55:52]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:6444kb
  • [2023-12-30 16:55:51]
  • 提交

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);
		for(auto p:conh[i]) cout<<p.x<<' '<<p.y<<endl;
	}
	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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 6444kb

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:

0 1
1 0
2 0
0 2
3
4
4

result:

wrong answer 1st numbers differ - expected: '3', found: '0'