QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#20530 | #2289. Jail or Joyride | The_Nobody# | WA | 3ms | 7800kb | C++14 | 3.2kb | 2022-02-16 14:40:40 | 2022-05-03 10:24:48 |
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 bfs(ll u){
q.push(u);vis[u]=1;
while(!q.empty()){
ll u=q.front();q.pop();
if(u==t)continue;
go(u)if(!vis[v]){
vis[v]=1;q.push(v);
}
}
rep(i,1,m){
if(x[i]==t&&vis[y[i]])tmp++,EE=i;
if(y[i]==t&&vis[x[i]])tmp++,EE=i;
}
}
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;
bfs(p);mem(vis,0);
mem(head,0);tot=0;
if(!tmp){puts("impossible");return 0;}
// puts("------");
// cout<<tmp<<' '<<EE<<endl;
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]]);
}
ll CAO=dis[p][t];
if(tmp!=1)q.push(t),vis[t]=1;
else{
mem(dis,0x3f);
rep(i,1,m)if(i!=EE)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];
// rep(i,1,top)cout<<s[i]<<" ";puts("");
}
// 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(-ans+CAO);
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 7676kb
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: 7732kb
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: 5616kb
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: -100
Wrong Answer
time: 2ms
memory: 7800kb
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:
4557430888798900974
result:
wrong answer 1st lines differ - expected: '2364', found: '4557430888798900974'