QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#20510#2289. Jail or JoyrideThe_Nobody#TL 4ms7812kbC++143.1kb2022-02-16 12:49:092022-05-03 10:19:55

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-03 10:19:55]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:7812kb
  • [2022-02-16 12:49:09]
  • 提交

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){
	if(tmp>1)return;
	vis[u]=1;
	if(u==t)EE=E,tmp++,DS=dis;
	go(u)if(!vis[v])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;
	dfs(p,0,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: 7588kb

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: 4ms
memory: 7796kb

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: 4ms
memory: 7708kb

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: 5660kb

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: 1ms
memory: 7760kb

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: 0ms
memory: 7812kb

input:

2 1 2 1
2 1 1

output:

1

result:

ok single line: '1'

Test #7:

score: -100
Time Limit Exceeded

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:


result: