QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#76593 | #5458. Shortest Path Query | futarian | WA | 88ms | 400972kb | C++14 | 1.7kb | 2023-02-10 21:36:26 | 2023-02-10 21:36:29 |
Judging History
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'