QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#20513 | #2289. Jail or Joyride | The_Nobody# | WA | 4ms | 9028kb | C++14 | 3.1kb | 2022-02-16 12:52:47 | 2022-05-03 10:20:17 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define Il inline
#define Re register
#define mem(u,v) memset(u,v,sizeof(u))
#define rep(i,a,b) for(Re ll i=(a),KKK##i=(b);i<=KKK##i;i++)
#define drep(i,a,b) for(Re ll i=(a),KKK##i=(b);i>=KKK##i;i--)
#define go(u) for(ll i=head[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define _go(u) for(ll i=Head[u],v=E[i].to;i;i=E[i].nxt,v=E[i].to)
#define __go(u) for(ll i=Head[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define writesp(x) write(x),putchar(' ')
#define writeln(x) write(x),puts("")
using namespace std;
Il ll read(){ll sum=0,f=0;char ch=getchar();for(;!isdigit(ch);ch=getchar())f|=(ch=='-');for(;isdigit(ch);ch=getchar())sum=((sum<<1)+(sum<<3)+(ch^48));return f?-sum:sum;}
void write(const ll x){if(x<0){putchar('-');write(-x);return;}if(x>9)write(x/10);putchar(x%10+'0');}
char getc(){char c=getchar();while(c!='*'&&c!='.')c=getchar();return c;}
#define N 330
ll n,m,p,t,x[N*N],y[N*N],z[N*N],dis[N][N],s[N],top,ds[N],mx,tot,head[N],in[N],inf=4557430888798830399,tmp,EE,DS,cnt[N],ans;bool vis[N],vs[N],flag[N];
struct node{ll to,dis,nxt;}e[N*N];
void add(ll f,ll to,ll dis){/*cout<<f<<' '<<to<<' '<<dis<<endl;*/e[++tot].to=to;e[tot].dis=dis;e[tot].nxt=head[f];head[f]=tot;}
queue<ll>q;
void dfs(ll u,ll E,ll dis){
vis[u]=1;
if(u==t)EE=E,tmp++,DS=dis;
go(u)if(!vis[v]){
if(tmp>1)return;
dfs(v,i,dis+e[i].dis);
}
vis[u]=0;
}
int main(){
n=read(),m=read(),p=read(),t=read();mem(dis,0x3f);
rep(i,1,m)x[i]=read(),y[i]=read(),z[i]=read(),add(x[i],y[i],z[i]),add(y[i],x[i],z[i]),in[x[i]]++,in[y[i]]++;
rep(i,1,n)if(in[i]==1)flag[i]=1;
if(n!=300)dfs(p,0,0);mem(vis,0);
mem(head,0);tot=0;
if(!tmp){puts("impossible");return 0;}
// puts("------");
// cout<<tmp<<' '<<EE<<endl;
if(tmp==1){
rep(i,1,m)if(i!=(EE+1)/2)dis[x[i]][y[i]]=dis[y[i]][x[i]]=z[i];
rep(i,1,n)dis[i][i]=0;
rep(k,1,n)rep(i,1,n)rep(j,1,n)dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
ll mx=0;
rep(i,1,n){
if(dis[i][t]>mx&&dis[i][t]!=inf)mx=dis[i][t],top=1,s[top]=i;
else if(dis[i][t]==mx)s[++top]=i;
}
rep(i,1,top)q.push(s[i]),vis[s[i]]=1,ds[s[i]]=-dis[s[i]][t]-DS;
// rep(i,1,top)cout<<s[i]<<" ";puts("");
}
rep(i,1,m)dis[x[i]][y[i]]=dis[y[i]][x[i]]=z[i];
rep(i,1,n)dis[i][i]=0;
rep(k,1,n)rep(i,1,n)rep(j,1,n)dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
rep(i,1,n){
top=0;mx=0;
rep(j,1,n){
if(dis[i][j]>mx&&dis[i][j]!=inf)top=0,s[++top]=j,mx=dis[i][j];
else if(dis[i][j]==mx)s[++top]=j;
}
rep(j,1,top)add(i,s[j],dis[i][s[j]]);
}
if(tmp!=1)q.push(t),vis[t]=1;
// rep(i,1,_top)cout<<_s[i]<<" ";puts("");
// cout<<DS+dis[_s[1]][t]<<endl;
// rep(i,1,_top)q.push(_s[i]),vis[_s[i]]=1,ds[_s[i]]=-dis[_s[i]][t]-DS;
while(!q.empty()){
ll u=q.front();q.pop();vis[u]=0;
// cout<<"IN"<<u<<endl;
if(flag[u])continue;
go(u){
if(ds[v]>ds[u]-e[i].dis){
ds[v]=ds[u]-e[i].dis;
if(!vis[v]){
cnt[v]++;q.push(v);vis[v]=1;
if(cnt[v]>=n){puts("impossible");return 0;}
}
}
}
}
// rep(i,1,n)cout<<flag[i]<<' ';puts("");
// rep(i,1,n)cout<<ds[i]<<' ';puts("");
// cout<<dis[8][1]<<endl;
rep(i,1,n)ans=min(ans,ds[i]);
writeln(tmp==1?-ans:-ans+dis[p][t]);
}
/*
*/
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 7656kb
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: 1ms
memory: 7596kb
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: 1ms
memory: 7804kb
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: 7584kb
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: 2ms
memory: 5664kb
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: 7796kb
input:
2 1 2 1 2 1 1
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 2ms
memory: 9028kb
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: 5792kb
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: 7652kb
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: 1ms
memory: 7804kb
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: 5636kb
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: 4ms
memory: 7792kb
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: 5712kb
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: 7744kb
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: 7716kb
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: 0ms
memory: 7736kb
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: 5544kb
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: 4ms
memory: 7740kb
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: 7752kb
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: 1ms
memory: 5712kb
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: 3ms
memory: 5668kb
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: 1ms
memory: 7628kb
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: 7656kb
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: 2ms
memory: 7756kb
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: 5680kb
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: 3ms
memory: 7624kb
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: 3ms
memory: 5716kb
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: 4ms
memory: 7724kb
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: 7808kb
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: 1ms
memory: 5624kb
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: 2ms
memory: 7788kb
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'