QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#19864 | #2289. Jail or Joyride | Appleblue17# | WA | 46ms | 4824kb | C++17 | 2.2kb | 2022-02-12 15:56:52 | 2022-05-06 07:22:44 |
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: 3704kb
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: 2ms
memory: 3680kb
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: 2ms
memory: 3684kb
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: 0ms
memory: 3652kb
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: 0ms
memory: 3656kb
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: 2ms
memory: 3728kb
input:
2 1 2 1 2 1 1
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 46ms
memory: 4824kb
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: 0ms
memory: 3728kb
input:
3 2 1 2 2 3 12 1 2 70
output:
82
result:
ok single line: '82'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3732kb
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: 3732kb
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: 3ms
memory: 3656kb
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: 3ms
memory: 3584kb
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: 1ms
memory: 3644kb
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: 1ms
memory: 3592kb
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: 3744kb
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: 3ms
memory: 3668kb
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: 2ms
memory: 3676kb
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: 3ms
memory: 3564kb
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: 3ms
memory: 3676kb
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: 3ms
memory: 3700kb
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: 0ms
memory: 3672kb
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: 3ms
memory: 3564kb
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: 3ms
memory: 3536kb
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: 3680kb
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: 3ms
memory: 3696kb
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: 2ms
memory: 3604kb
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: 3564kb
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: 3ms
memory: 3572kb
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: 3ms
memory: 3752kb
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: 3ms
memory: 3684kb
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: 4808kb
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'