QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#19865 | #2289. Jail or Joyride | Xiao_Luo_Xuan | WA | 45ms | 4880kb | C++17 | 2.2kb | 2022-02-12 15:58:59 | 2022-05-06 07:22:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=330,M=1e5+5,INF=1e9;
int n,m,p,t,ans;
int dis[N][N],in[N],diss[N][N];
int F[N][N],G[N][N];
int Dis[N],num[N];
bool Vis[N];
queue <int> q;
bool vis[N];
void floyd(int dis[N][N]){
for(int k=1;k<=n;k++)
for(int u=1;u<=n;u++)
for(int v=1;v<=n;v++)
dis[u][v]=min(dis[u][v],dis[u][k]+dis[k][v]);
}
void dfs(int u,int ban){
if(u==ban || vis[u]) return ;
vis[u]=1;
for(int v=1;v<=n;v++){
if(u==v || F[u][v]==INF) continue;
dfs(v,ban);
}
}
void pr(int f[N][N]){
cout<<"pr: "<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cout<<f[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
int main(){
cin>>n>>m>>p>>t;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=F[i][j]=G[i][j]=INF;
for(int i=1;i<=n;i++) dis[i][i]=F[i][i]=G[i][i]=0;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
in[u]++,in[v]++;
dis[u][v]=min(G[u][v],w);
dis[v][u]=min(G[v][u],w);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
F[i][j]=dis[i][j];
floyd(dis);
dfs(p,t);
// pr(dis);
int tot=0,sav;
for(int v=1;v<=n;v++){
if(v==t || F[t][v]==INF) continue;
if(vis[v]) tot++,sav=v;
}
for(int i=1;i<=n;i++) Dis[i]=-INF;
if(tot==1){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
diss[i][j]=F[i][j];
diss[sav][t]=diss[t][sav]=INF;
// pr(diss);
floyd(diss);
int mx=0;
for(int i=1;i<=n;i++) if(diss[t][i]<INF) mx=max(mx,diss[t][i]);
for(int i=1;i<=n;i++)
if(mx==diss[t][i]) Dis[i]=dis[t][i],q.push(i),Vis[i]=1;
}
else Dis[t]=0,q.push(t),Vis[t]=1;
for(int u=1;u<=n;u++){
int mx=0;
for(int i=1;i<=n;i++) if(dis[u][i]<INF) mx=max(mx,dis[u][i]);
for(int i=1;i<=n;i++) if(mx==dis[u][i]) G[u][i]=dis[u][i];
}
// pr(G);
while(q.size()){
int u=q.front();
q.pop();
Vis[u]=0;
if(in[u]==1) continue;
for(int v=1;v<=n;v++){
if(u==v || G[u][v]==INF) continue;
Dis[v]=max(Dis[v],Dis[u]+G[u][v]);
if(!Vis[v]){
q.push(v),Vis[v]=1;
num[v]++;
if(num[v]>n) return puts("impossible"),0;
}
}
}
for(int i=1;i<=n;i++){
if(in[i]==1){
ans=max(ans,dis[p][t]+Dis[i]);
}
}
cout<<ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3760kb
input:
9 10 1 2 1 2 225869 2 3 1772 3 4 314393 4 5 692250 5 6 684107 4 6 532792 3 7 441133 7 8 468183 8 9 186297 7 9 228792
output:
impossible
result:
ok single line: 'impossible'
Test #2:
score: 0
Accepted
time: 3ms
memory: 3620kb
input:
9 10 3 2 1 2 225869 2 3 1772 3 4 314393 4 5 692250 5 6 684107 4 6 532792 3 7 441133 7 8 468183 8 9 186297 7 9 228792
output:
227641
result:
ok single line: '227641'
Test #3:
score: 0
Accepted
time: 3ms
memory: 3664kb
input:
8 22 8 1 1 2 11 1 3 11 1 4 11 1 5 11 1 6 11 1 7 10 2 3 12 2 4 12 2 5 12 2 6 12 2 7 11 3 4 13 3 5 13 3 6 13 3 7 12 4 5 14 4 6 14 4 7 13 5 6 15 5 7 14 6 7 15 7 8 1
output:
92
result:
ok single line: '92'
Test #4:
score: 0
Accepted
time: 3ms
memory: 3608kb
input:
6 7 3 6 1 3 2642 3 4 1253 2 4 64316 2 5 235162 6 5 2341 5 3 23 5 4 589201
output:
2364
result:
ok single line: '2364'
Test #5:
score: 0
Accepted
time: 3ms
memory: 3736kb
input:
4 4 3 2 1 2 1 2 3 10 2 4 5 4 3 6
output:
31
result:
ok single line: '31'
Test #6:
score: 0
Accepted
time: 3ms
memory: 3660kb
input:
2 1 2 1 2 1 1
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 45ms
memory: 4876kb
input:
300 44850 247 85 272 228 288849537 241 43 9873162 189 240 10538237 136 291 880425990 91 207 56502487 7 277 568371880 251 9 636070665 166 7 628732259 130 183 203171884 7 12 786299190 285 280 282670657 180 263 699873645 63 207 872780899 271 245 230237525 123 58 404988100 34 217 990722599 259 50 355842...
output:
impossible
result:
ok single line: 'impossible'
Test #8:
score: 0
Accepted
time: 3ms
memory: 3632kb
input:
3 2 1 2 2 3 12 1 2 70
output:
82
result:
ok single line: '82'
Test #9:
score: 0
Accepted
time: 3ms
memory: 3664kb
input:
3 3 1 3 1 3 1 2 3 1 1 2 1
output:
impossible
result:
ok single line: 'impossible'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
4 4 3 2 3 1 1 3 4 1 2 1 1 2 4 1
output:
impossible
result:
ok single line: 'impossible'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
4 4 2 1 3 1 5 1 4 3 2 1 5 2 4 5
output:
20
result:
ok single line: '20'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
4 4 2 4 3 4 7 4 2 5 1 2 5 3 2 5
output:
15
result:
ok single line: '15'
Test #13:
score: 0
Accepted
time: 3ms
memory: 3596kb
input:
4 4 2 3 2 1 10 1 4 9 4 2 2 1 3 3
output:
13
result:
ok single line: '13'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
4 4 3 4 3 2 9 4 2 13 1 2 20 1 4 16
output:
44
result:
ok single line: '44'
Test #15:
score: 0
Accepted
time: 3ms
memory: 3736kb
input:
4 4 4 2 4 3 368412026 4 2 248686681 1 3 856765094 3 2 319358821
output:
1424810596
result:
ok single line: '1424810596'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3520kb
input:
4 5 3 2 3 1 3 4 2 7 4 3 17 2 3 14 2 1 4
output:
impossible
result:
ok single line: 'impossible'
Test #17:
score: 0
Accepted
time: 3ms
memory: 3584kb
input:
4 6 1 2 1 4 1 2 4 1 2 3 1 1 3 1 4 3 1 1 2 1
output:
impossible
result:
ok single line: 'impossible'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
5 5 4 5 1 5 1 3 5 1 2 1 2 3 4 2 2 4 2
output:
impossible
result:
ok single line: 'impossible'
Test #19:
score: 0
Accepted
time: 2ms
memory: 3672kb
input:
5 6 3 4 3 4 3 1 5 2 4 2 3 2 3 2 1 4 1 5 3 1
output:
impossible
result:
ok single line: 'impossible'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
5 6 3 2 1 5 10 3 1 8 3 5 6 3 4 7 1 4 6 1 2 6
output:
14
result:
ok single line: '14'
Test #21:
score: 0
Accepted
time: 2ms
memory: 3732kb
input:
5 7 5 1 1 2 1 4 2 1 2 5 1 4 3 1 1 4 1 1 5 1 1 3 1
output:
impossible
result:
ok single line: 'impossible'
Test #22:
score: 0
Accepted
time: 2ms
memory: 3736kb
input:
5 8 2 1 3 2 218 2 1 176 5 1 177 5 2 248 5 3 249 3 1 110 2 4 24 1 4 269
output:
impossible
result:
ok single line: 'impossible'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
6 6 2 6 4 5 34 4 2 13 6 4 18 3 6 3 1 2 15 1 6 2
output:
69
result:
ok single line: '69'
Test #24:
score: 0
Accepted
time: 3ms
memory: 3600kb
input:
6 7 2 4 6 1 5 2 4 3 3 5 5 5 4 2 4 3 1 6 2 5 6 3 6
output:
15
result:
ok single line: '15'
Test #25:
score: 0
Accepted
time: 2ms
memory: 3680kb
input:
6 8 3 5 3 5 5 4 1 6 5 2 9 5 1 10 1 6 1 3 2 10 4 6 1 2 6 6
output:
impossible
result:
ok single line: 'impossible'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
7 7 4 2 3 6 1 3 5 1 1 7 1 1 5 1 5 4 1 7 3 1 4 2 1
output:
1
result:
ok single line: '1'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
7 8 6 2 2 5 5 3 2 1 4 6 10 2 6 3 1 2 6 5 3 4 7 4 9 4 2 2
output:
14
result:
ok single line: '14'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
7 10 2 5 4 2 5 5 4 3 2 5 5 1 3 4 1 6 7 1 5 6 3 7 1 6 4 6 5 3 6 7 1 3
output:
impossible
result:
ok single line: 'impossible'
Test #29:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
7 10 5 2 3 6 39 7 2 38 1 3 5 2 3 38 4 2 8 1 4 26 5 6 9 2 6 12 7 5 10 5 2 20
output:
impossible
result:
ok single line: 'impossible'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
10 20 7 4 5 1 326 2 3 264 10 4 132 5 3 279 5 8 215 7 10 161 3 6 51 4 9 184 5 10 183 8 1 26 7 3 27 4 5 215 6 8 8 8 7 166 4 3 272 8 9 176 1 9 336 7 2 276 9 10 190 2 1 239
output:
impossible
result:
ok single line: 'impossible'
Test #31:
score: -100
Wrong Answer
time: 19ms
memory: 4880kb
input:
300 1000 172 215 188 170 616047457 52 84 278955639 40 242 753349504 163 138 601228798 161 16 632160688 179 229 448530394 69 143 427101036 289 245 202138801 196 67 997170084 39 117 521910244 280 119 344655702 79 105 274646714 241 183 674512683 113 66 937810400 273 93 112339663 3 233 976547617 250 290...
output:
impossible
result:
wrong answer 1st lines differ - expected: '5348814077', found: 'impossible'