QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#76593#5458. Shortest Path QueryfutarianWA 88ms400972kbC++141.7kb2023-02-10 21:36:262023-02-10 21:36:29

Judging History

你现在查看的是测评时间为 2023-02-10 21:36:29 的历史记录

  • [2024-06-21 12:37:39]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:66ms
  • 内存:402896kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-10 21:36:29]
  • 评测
  • 测评结果:0
  • 用时:88ms
  • 内存:400972kb
  • [2023-02-10 21:36:26]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
#define ll long long
const int M = 5e7 + 5 , Len = 1e5 + 5;
const ll Inf = 1e12;
struct node
{
	int x,y;
	node(){x = y = 0;}
	node(int X,int Y){x = X , y = Y;}
	bool operator < (const node &Ano) const
	{return x < Ano.x || (x == Ano.x && y < Ano.y);}
	ll operator ^ (const node &Ano) const
	{return x * Ano.y - y * Ano.x;}
	node operator - (const node &Ano) const
	{return node(x - Ano.x , y - Ano.y);}
}stk[M];int top;
vector<node> vc[Len];
int head[Len],cnt,n,m,q;
struct Node
{
	int next,to,w;
}edge[Len << 1];
inline void add(int from,int to,int w)
{
	edge[++ cnt].to = to;
	edge[cnt].w = w;
	edge[cnt].next = head[from];
	head[from] = cnt;
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i = 1 ; i <= m ; i ++){int u,v,w;scanf("%d %d %d",&u,&v,&w);add(u , v , w);}
	vc[1].push_back(node(0 , 0));
	for(int i = 1 ; i <= n ; i ++)
	{
		sort(vc[i].begin() , vc[i].end());top = 0;const int SZ = (int)vc[i].size();
		for(int j = 0 ; j < SZ ; j ++)
		{
			while(top > 1 && ((stk[top] - stk[top - 1]) ^ (vc[i][j] - stk[top - 1])) >= 0) top --;
			stk[++ top] = vc[i][j]; 
		}
		vector<node> pw;swap(pw , vc[i]);vc[i].reserve(top);
		for(int j = 0 ; j < top ; j ++) vc[i].push_back(stk[j + 1]);
		for(int e = head[i] ; e ; e = edge[e].next)
		{
			int to = edge[e].to;
			for(int j = 1 ; j <= top ; j ++) vc[to].push_back(node(stk[j].x + (edge[e].w == 0) , stk[j].y + (edge[e].w == 1)));
		}
	}	scanf("%d",&q);
	for(int i = 1 ; i <= q ; i ++)
	{
		int a,b,x;scanf("%d %d %d",&a,&b,&x);
		const int SZ = (int)vc[x].size();ll as = Inf;
		for(int j = 0 ; j < SZ ; j ++) as = min(as , 1ll * a * vc[x][j].x + 1ll * b * vc[x][j].y);
		printf("%lld\n",as);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 32ms
memory: 396592kb

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: 88ms
memory: 400972kb

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:

171090050
250459598
258589143
259699419
104338880
16685198
59196446
64713954
46949896
245672377
94777502
84753103
267419449
192242757
216482422
147454419
111021650
80187604
247374700
111782626
121405290
249524638
191332392
202049239
343798460
173714177
174899498
97998224
96431009
280559577
164349486...

result:

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