QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#673007#3043. Lexicographically Minimum WalktbdshWA 8ms72076kbC++141.2kb2024-10-24 20:16:482024-10-24 20:16:50

Judging History

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

  • [2024-10-24 20:16:50]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:72076kb
  • [2024-10-24 20:16:48]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
const int MAXN = 1e5 + 5;
int n, m, s, t;
struct Node{
  int v, w;
};
vector<int> a, ans;
vector<Node> g[MAXN];
bool operator<(const vector<int> &a, const vector<int> &b){
  if (a.size() != b.size()){
    return a.size() < b.size();
  }
  for (int i = 0; i < a.size(); i++){
    if (a[i] != b[i]){
      return a[i] < b[i];
    }
  }
  return 0;
}
void dfs(int x){
  if (a.size() > 1e6){
    cout << "TOO LONG";
    exit(0);
  }else if (x == t){
    // for (auto v : a){
    //   cerr << v << ' ';
    // }
    // cerr << '\n';
    // for (auto v : ans){
    //   cerr << v << ' ';
    // }
    // cerr << '\n' << (ans > a) << "\n\n";
    if (ans < a){
      ans = a;
    }
    return ;
  } 
  for (auto v : g[x]){
    a.push_back(v.w);
    dfs(v.v);
    a.pop_back();
  }
}
signed main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> s >> t;
  while (m--){
    int u, v, c;
    cin >> u >> v >> c;
    g[u].push_back({v, c});
  }
  dfs(s);
  if (!ans.size()){
    cout << "IMPOSSIBLE";
  }else {
    for (auto v : ans){
      cout << v << ' ';
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5908kb

input:

3 3 1 3
1 2 1
2 3 7
1 3 5

output:

1 7 

result:

ok single line: '1 7 '

Test #2:

score: 0
Accepted
time: 0ms
memory: 72076kb

input:

3 4 1 3
1 2 1
2 1 2
2 3 7
1 3 5

output:

TOO LONG

result:

ok single line: 'TOO LONG'

Test #3:

score: 0
Accepted
time: 1ms
memory: 5952kb

input:

2 0 2 1

output:

IMPOSSIBLE

result:

ok single line: 'IMPOSSIBLE'

Test #4:

score: -100
Wrong Answer
time: 8ms
memory: 72024kb

input:

4 4 1 4
1 2 3
2 3 1
3 1 6
3 4 5

output:

TOO LONG

result:

wrong answer 1st lines differ - expected: '3 1 5', found: 'TOO LONG'