QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#670356 | #3038. Bigger Sokoban 40k | PNNNN | TL | 0ms | 0kb | C++14 | 1.4kb | 2024-10-23 21:26:21 | 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;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
What do you think?