QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#560159 | #8673. 最短路径 | AllenJYL | 0 | 1624ms | 186208kb | C++14 | 3.8kb | 2024-09-12 13:43:55 | 2024-09-12 13:44:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
// #define int128 __int128_t
#define ls p<<1
#define rs p<<1|1
#define msp(_array) memset(_array,0x3f,sizeof _array)
#define ms0(_array) memset(_array,0,sizeof _array)
#define msn(_array) memset(_array,-1,sizeof _array)
#define mc(_tar,_array) memcpy(_tar,_array,sizeof _tar)
#define pii pair<int,int>
#define endl '\n'
bool bg_memory;
const int mod=(1ll<<60)-1;
const int inf=1e18;
const int bs=23333;
const double eps=1e-6;
const int N=2e5+7,M=3e6+7;
inline void cmax(int &a,int b){a=a<b?b:a;}
inline void cmin(int &a,int b){a=a>b?b:a;}
int n,m,q,seed;
int s,t,o;
vector<pii> e[N],r[N];
int dis[N][3],cl[N];
int ans;
set<int> ap;
void generate_edges(){
std::mt19937 gen(seed);
unsigned max = -1u / n * n;
auto sample = [&]() {
unsigned x;
do { x = gen(); } while(x >= max);
return x % n + 1;
};
for(int i=1;i<=m;i++){
int u=sample();
int v=sample();
int w=gen();
e[u].push_back({v,w});
r[v].push_back({u,w});
}
}
priority_queue<pii,vector<pii>,greater<> > ps,pt;
void dij(){
for(int i:ap) dis[i][1]=dis[i][2]=0x3f3f3f3f3f3f3f3f,cl[i]=0;
ap.clear();
dis[s][1]=dis[t][2]=0;
while(ps.size()) ps.pop();
while(pt.size()) pt.pop();
ps.emplace(0,s);
pt.emplace(0,t);
ap.insert(s);
ap.insert(t);
while(ps.size()){
int x=ps.top().second;
ps.pop();
if(!cl[x]){
cl[x]=1;
for(pii i:e[x]){
if(dis[i.first][1]>dis[x][1]+i.second){
ap.insert(i.first);
dis[i.first][1]=dis[x][1]+i.second;
ps.emplace(dis[i.first][1],i.first);
}
}
}else if(cl[x]==2) return o=x,void();
// x=pt.top().second;
// pt.pop();
// if(!cl[x]){
// cl[x]=2;
// for(pii i:r[x]){
// if(dis[i.first][2]>dis[x][2]+i.second){
// ap.insert(i.first);
// dis[i.first][2]=dis[x][2]+i.second;
// pt.emplace(dis[i.first][2],i.first);
// }
// }
// }else if(cl[x]==1) return o=x,void();
}
}
mt19937 rnd(time(0));
int Case=1;
void Main(){
cin>>n>>m>>q>>seed;
generate_edges();
for(int i=1;i<=n;i++) sort(e[i].begin(),e[i].end(),[](pii a,pii b){return a.second<b.second;});
for(int i=1;i<=n;i++) sort(r[i].begin(),r[i].end(),[](pii a,pii b){return a.second<b.second;});
msp(dis);
for(int i=1;i<=(n==4?q:3);i++){
cin>>s>>t;
o=0;
dij();
if(!o){
cout<<-1<<endl;
continue;
}
ans=dis[o][1]+dis[o][2];
for(int j:ap){
if(cl[j]==1){
for(pii k:e[j]){
if(k.second>2*(dis[o][1]-dis[j][1])) break;
cmin(ans,dis[j][1]+dis[k.first][2]+k.second);
}
}
}
cout<<ans<<endl;
}
return;
}
string RdFile="c";
bool en_memory;
signed main(){
auto bg_clock=chrono::high_resolution_clock::now();
#ifdef ONLINE_JUDGE
// freopen((RdFile+".in").c_str(),"r",stdin);
// freopen((RdFile+".out").c_str(),"w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// cin>>Case;
while(Case--) Main();
auto en_clock=chrono::high_resolution_clock::now();
auto duration_clock=chrono::duration_cast<chrono::microseconds>(en_clock-bg_clock);
#ifndef ONLINE_JUDGE
cerr<<endl<<"code_time_used: "<<duration_clock.count()*0.001<<"ms"<<endl;
cerr<<"code_memory_used: "<<(&en_memory-&bg_memory)/1024.0/1024<<"MB"<<endl;
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 18696kb
input:
4 8 5 1112792816 2 3 4 3 4 3 3 2 1 4
output:
-1 -1 -1 -1 -1
result:
wrong answer 1st lines differ - expected: '3419197189', found: '-1'
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 375ms
memory: 142448kb
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:
-1 -1 -1
result:
wrong answer 1st lines differ - expected: '36084543', found: '-1'
Subtask #3:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 33ms
memory: 29548kb
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:
-1 -1 -1
result:
wrong answer 4th lines differ - expected: '-1', found: ''
Subtask #4:
score: 0
Wrong Answer
Test #17:
score: 0
Wrong Answer
time: 366ms
memory: 53724kb
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:
-1 -1 -1
result:
wrong answer 1st lines differ - expected: '21671419385', found: '-1'
Subtask #5:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 512ms
memory: 53708kb
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:
-1 -1 -1
result:
wrong answer 1st lines differ - expected: '18098332289', found: '-1'
Subtask #6:
score: 0
Wrong Answer
Test #24:
score: 0
Wrong Answer
time: 966ms
memory: 180488kb
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:
-1 -1 -1
result:
wrong answer 1st lines differ - expected: '1547972368', found: '-1'
Subtask #7:
score: 0
Wrong Answer
Test #33:
score: 0
Wrong Answer
time: 1624ms
memory: 186208kb
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:
-1 -1 -1
result:
wrong answer 1st lines differ - expected: '3371897180', found: '-1'