QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#670356#3038. Bigger Sokoban 40kPNNNNTL 0ms0kbC++141.4kb2024-10-23 21:26:212024-10-23 21:26:21

Judging History

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

  • [2024-10-23 21:26:21]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-10-23 21:26:21]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define fr first
#define sc second
#define lowbit(x) x&-x
using namespace std;

int n,m,S,T,flag;

struct line{
	int y,w;
};vector <line> to[100005];

inline bool cmp(line A,line B){
	return A.w<B.w;
}

int vis[100005];

pair<int,int> pre[100005];

inline void dfs(int x){
	vis[x]=1;
	for(int i=0;i<to[x].size();i++){
		int y=to[x][i].y,w=to[x][i].w;
		if(vis[y])continue;
		pre[y]={x,w},dfs(y);
	}return;
}

vector <int> ans;

inline void solve(){
	int cur=T;
	if(!pre[T].fr)return;
	while(cur!=S){
		if(cur!=T){
			for(auto nxt:to[cur]){
				if(nxt.y==pre[cur].fr&&nxt.w<ans.back()){
					flag=1;
				}
			}
		}
		ans.push_back(pre[cur].sc);
		cur=pre[cur].fr;
	}return;
}

inline int read(){
	register int x=0,t=0;
	static char ch=getchar();
	while(!isdigit(ch))t|=(ch=='-'),ch=getchar();
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return t?-x:x;
}

signed main(){
	
	n=read(),m=read(),S=read(),T=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),w=read();
		to[x].push_back({y,w});
	}
	for(int i=1;i<=n;i++){
		sort(to[i].begin(),to[i].end(),cmp);
	}
	dfs(S),solve();
	
	if(!ans.size()){
		cout<<"IMPOSSIBLE";
		return 0;
	}
	if(flag){
		cout<<"TOO LONG";
		return 0;
	}
	for(int i=ans.size()-1;i>=0;i--){
		cout<<ans[i]<<' ';
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

What do you think?

output:


result: