10133 | 2024-03-27 20:24:06 | 111 | Vázsony vonatjegyet vásárol | cpp17 | Hibás válasz 0/100 | 1.572s | 121584 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
template<typename T>
using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,M,A,B;
cin>>N>>M>>A>>B;
vector<vector<tuple<int,int,int>>>g(N+1);
for(int i=0;i<M;i++){
int a,b,w;
cin>>a>>b>>w;
g[a].emplace_back(b,w,i);
g[b].emplace_back(a,w,i);
}
vector<int>c(N+1,INF);
min_priority_queue<pair<int,int>>pq;
c[B]=0;
pq.emplace(0,B);
while(!pq.empty()){
auto[d,i]=pq.top();
pq.pop();
if(d>c[i]){
continue;
}
for(auto[j,w,_]:g[i]){
if(c[i]+w<c[j]){
c[j]=c[i]+w;
pq.emplace(c[j],j);
}
}
}
vector<int>ans,a;
int ansc=0,ac=0;
vector<int>v(N+1),w(M);
int st=clock();
auto bt=[&](auto self,int i)->void{
if(clock()-st>CLOCKS_PER_SEC)return;
if(v[i]==0){
ac++;
}
v[i]++;
a.push_back(i);
if(i==B){
if(ac>ansc){
ansc=ac;
ans=a;
}
}
else{
for(auto[j,_,k]:g[i]){
if(w[k]>=2){
continue;
}
w[k]++;
if(c[j]<=c[i]){
self(self,j);
}
w[k]--;
}
}
a.pop_back();
v[i]--;
if(v[i]==0){
ac--;
}
};
bt(bt,A);
sort(ans.begin(),ans.end());
ans.erase(unique(ans.begin(),ans.end()),ans.end());
cout<<ans.size()<<'\n';
for(int i:ans){
cout<<i<<' ';
}
cout<<'\n';
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1828 KiB | ||||
2 | Hibás válasz | 1.108s | 32568 KiB | ||||
subtask2 | 0/20 | ||||||
3 | Hibás válasz | 1.047s | 16824 KiB | ||||
4 | Hibás válasz | 1.31s | 83788 KiB | ||||
5 | Hibás válasz | 1.258s | 66356 KiB | ||||
6 | Hibás válasz | 1.203s | 52488 KiB | ||||
7 | Hibás válasz | 1.238s | 67240 KiB | ||||
8 | Hibás válasz | 1.21s | 52016 KiB | ||||
9 | Hibás válasz | 1.435s | 109108 KiB | ||||
subtask3 | 0/15 | ||||||
10 | Hibás válasz | 1.312s | 64192 KiB | ||||
11 | Elfogadva | 9ms | 9344 KiB | ||||
12 | Hibás válasz | 1.018s | 10260 KiB | ||||
13 | Hibás válasz | 1.054s | 20256 KiB | ||||
14 | Hibás válasz | 1.065s | 36208 KiB | ||||
subtask4 | 0/20 | ||||||
15 | Hibás válasz | 1.052s | 30876 KiB | ||||
16 | Hibás válasz | 1.159s | 47208 KiB | ||||
17 | Hibás válasz | 1.029s | 22928 KiB | ||||
18 | Hibás válasz | 1.054s | 29872 KiB | ||||
19 | Hibás válasz | 1.031s | 16488 KiB | ||||
20 | Hibás válasz | 1.06s | 26048 KiB | ||||
subtask5 | 0/45 | ||||||
21 | Hibás válasz | 1.003s | 7392 KiB | ||||
22 | Időlimit túllépés | 1.572s | 78712 KiB | ||||
23 | Hibás válasz | 1.037s | 20368 KiB | ||||
24 | Hibás válasz | 1.174s | 56064 KiB | ||||
25 | Hibás válasz | 1.159s | 48856 KiB | ||||
26 | Hibás válasz | 1.276s | 71352 KiB | ||||
27 | Elfogadva | 1.024s | 48268 KiB | ||||
28 | Hibás válasz | 1.486s | 121584 KiB | ||||
29 | Hibás válasz | 1.106s | 36032 KiB | ||||
30 | Hibás válasz | 1.424s | 102612 KiB | ||||
31 | Hibás válasz | 1.192s | 49212 KiB | ||||
32 | Hibás válasz | 1.039s | 23300 KiB | ||||
33 | Hibás válasz | 1.276s | 67080 KiB | ||||
34 | Hibás válasz | 1.274s | 60628 KiB | ||||
35 | Hibás válasz | 1.277s | 60668 KiB | ||||
36 | Hibás válasz | 1.279s | 60768 KiB | ||||
37 | Hibás válasz | 1.276s | 60920 KiB |