QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #560545 | #8673. 最短路径 | Juefan | 0 | 1246ms | 215120kb | C++20 | 2.8kb | 2024-09-12 16:18:04 | 2024-09-12 16:18:08 |
Judging History
answer
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a,i##E=b;i<=i##E;i++)
#define UF(i,a,b) for(int i=a,i##E=b;i>=i##E;i--)
#define sz(x) int(x.size())
using namespace std;typedef long long ll;
#define vec vector
template<typename T>
void operator+=(vec<T> &a,const T&b) {a.push_back(b);}
#define gc() getchar()
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char *p1,*p2,buf[1<<21];
unsigned read() {
unsigned s=0,w=0;char ch=gc();
while(ch<'0'||ch>'9') w|=(ch=='-'),ch=gc();
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=gc();
return w?-s:s;
}
std::vector<std::tuple<int, int, long long>> generate_edges(int n, int m, unsigned seed) {
std::mt19937 gen(seed);
std::vector<std::tuple<int, int, long long>> edges(m);
unsigned max = -1u / n * n;
auto sample = [&]() {
unsigned x;
do { x = gen(); } while(x >= max);
return x % n + 1;
};
for(auto & [u, v, w] : edges) {
u = sample();
v = sample();
w = gen();
} // u 到 v 存在边权为 w 的边
return edges;
} const int N=2e5+5;
const ll inf=1e18;
int n,m,q;
struct E{int v;ll w;bool operator<(E b)const{return w<b.w;}};
vec<E> G[N][2];
using T=tuple<ll,int,int,bool>;
ll d[N][2];int now[N][2];
ll sol(int s,int t) {
if(!sz(G[s][0])||!sz(G[t][1])) return -1;
priority_queue<T,vec<T>,greater<T>> q;
auto Push=[&](int x,int i,int r,const int type=0) {
auto[v,w]=G[x][r][i];
if(d[x][r]+w<d[v][r]) q.push({d[v][r]=d[x][r]+w,v,x,r});
else if(type) q.push({d[v][r],v,x,r});
};
d[s][0]=0;d[t][1]=0;
Push(s,0,0,1);Push(t,0,1,1);
vec<int> V[2];
int X=-1;V[0]+=s;V[1]+=t;ll ans=inf;
while(!q.empty()) {
auto[D,x,p,r]=q.top();q.pop();
// cerr<<"QIUEUEUEUEUE::"<<D<<" "<<x<<' '<<d[x][r]<<' '<<p<<' '<<r<<endl;
if(d[x][0]<inf&&d[x][1]<inf) {X=x;ans=d[x][0]+d[x][1];break;}
if(++now[p][r]<sz(G[p][r])) {
Push(p,now[p][r],r,1);
}
if(D>d[x][r]) continue;
V[r]+=x;Push(x,0,r);
}
#define x X
for(int y:V[0]) for(auto[v,w]:G[y][0])
if(w<2*(d[x][0]-d[y][0])) ans=min(ans,d[y][0]+w+d[v][1]);
else break;
for(int y:V[1]) for(auto[v,w]:G[y][1])
if(w<2*(d[x][1]-d[y][1])) ans=min(ans,d[y][1]+w+d[v][0]);
else break;
for(int y:V[0]) d[y][0]=inf,now[y][0]=0;
for(int y:V[1]) d[y][1]=inf,now[y][1]=0;
while(sz(q)) {
auto[D,x,p,r]=q.top();q.pop();
d[x][r]=inf;now[p][r]=0;
}
return ans>=inf?-1:ans;
#undef x
}
int main() {
n=read();m=read();q=read();
auto Edges=generate_edges(n,m,read());
for(auto[u,v,w]:Edges) G[u][0]+=E{v,w},G[v][1]+=E{u,w};//,cerr<<"K::"<<u<<' '<<v<<' '<<w<<endl;
F(i,1,n) F(j,0,1) sort(begin(G[i][j]),end(G[i][j]));
F(j,0,1) F(i,1,n) d[i][j]=inf;
F(i,1,q) {
int x=read(),y=read();
cout<<sol(x,y)<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 5
Accepted
time: 1ms
memory: 3600kb
input:
4 8 5 1112792816 2 3 4 3 4 3 3 2 1 4
output:
3419197189 1798364963 1798364963 3986398077 2337967903
result:
ok 5 lines
Test #2:
score: 0
Runtime Error
input:
2000 2000 2000 3336994405 659 1650 1678 341 818 235 1380 1865 1927 1366 1233 1673 267 1698 775 1022 1255 1110 1533 1928 1854 169 1579 729 449 1335 943 583 360 50 795 926 1584 911 1924 604 280 309 1429 420 1107 1858 1466 76 265 1109 1077 622 245 1941 957 1434 1560 1128 122 51 229 925 826 1006 851 323...
output:
result:
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 365ms
memory: 175780kb
input:
3000 3000000 10000 37461678 2873 1368 1757 2000 1262 1822 2484 1778 2055 2096 2545 366 2923 2028 1469 1874 691 631 1173 2967 894 2020 1207 881 373 236 1913 1923 1351 16 1066 2032 471 1561 1047 2043 457 145 2728 1752 2521 1199 1568 904 2515 543 1472 2161 748 2744 748 1908 912 172 2340 2494 977 267 10...
output:
36084543 49860181 45803385 27805775 41392651 43506617 39517515 39687913 37675345 23367579 37276839 32364058 50703016 26615083 25983590 51209814 36451810 24398516 33216605 21796337 36267824 60108033 34199475 45804995 24398516 24398516 38718065 54032115 31005342 41408425 35033769 37667712 20240934 378...
result:
wrong answer 17th lines differ - expected: '42921191', found: '36451810'
Subtask #3:
score: 0
Runtime Error
Test #13:
score: 0
Runtime Error
input:
200000 200000 10000 1824322211 104482 112162 130667 13436 36792 142259 51832 97549 15358 180076 128251 92635 45296 195115 62109 38014 22014 86754 79735 103777 94797 96086 196760 5955 45622 59618 12995 62585 55686 156402 23085 68138 170749 148553 97603 160274 112975 22651 116322 190720 84774 57075 23...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #17:
score: 0
Runtime Error
input:
200000 500000 10000 3113327438 68816 31422 174349 125983 18111 188786 84806 87249 142007 180723 95611 116398 104758 196349 77547 89859 120350 77199 110906 10209 177461 194861 115505 105566 27493 166237 15676 158290 86204 116010 159979 125659 132461 61989 194289 157721 18830 82910 166696 98162 125208...
output:
result:
Subtask #5:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
input:
200000 500000 10000 1843053063 3409 108359 168924 184622 13119 119837 109492 38050 97152 51201 49047 12472 183998 191613 193074 177289 194248 104409 15509 88499 61967 143398 4532 56790 196650 158711 63655 70744 140178 107299 63530 87330 127334 159237 7134 184418 125289 28604 176966 179527 181695 128...
output:
result:
Subtask #6:
score: 0
Wrong Answer
Test #24:
score: 0
Wrong Answer
time: 1246ms
memory: 215120kb
input:
100000 3000000 10000 3892765041 14843 34156 43390 49542 38564 95501 26194 87126 18638 53346 69414 47011 95472 58303 44370 77172 75652 90555 94386 31888 47911 9905 70599 97061 52764 24896 31445 15589 82314 43852 97155 93412 11834 45082 75614 42459 67802 32024 82389 4968 32860 62514 97630 28012 14839 ...
output:
1547972368 1551270526 1192488694 1802115335 1632623563 1888896300 1720188008 1762089620 1815841406 1831208977 1250925907 1756812381 2002575767 1385409721 1776291520 1877583272 1632784703 2090242303 1483818292 1570260863 1429598050 1599437722 2286394605 1416358110 1929044811 2022891575 1487757623 118...
result:
wrong answer 2nd lines differ - expected: '1533240012', found: '1551270526'
Subtask #7:
score: 0
Runtime Error
Test #33:
score: 0
Runtime Error
input:
200000 3000000 10000 3910662331 161257 40967 50546 86049 199665 199302 177403 36274 158790 143151 193304 78511 28032 149723 96394 37099 2157 76024 195400 34830 41933 147591 191613 96468 194837 67293 57992 63117 24749 6694 117818 87323 46130 53470 174812 24950 149173 124886 119910 54123 2297 124533 5...
output:
3371897180 3059012504 3906003323 5021405654 3885338786 3101758258 4211432244 3706642516 3320322266 4020388668 3314213999 4273862043 3045843635 3379778417 3201003504 4882412858 4847106102 3502897631 3579081638 3470448652 4322207527 2160161436 4372954162 3841655899 3367608876 3864513044 4225021719 377...