10130 | 2024-03-27 20:11:12 | 111 | Vázsony vonatjegyet vásárol | cpp17 | Hibás válasz 0/100 | 1.6s | 98156 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<pair<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);
g[b].emplace_back(a,w);
}
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>v(N+1),a(N+1),b(N+1);
int ap=0,bp=0;
int it=0;
auto bt=[&](auto self,int i)->void{
if(it++>100000000){
return;
}
if(v[i]){
return;
}
v[i]=1;
a[ap++]=i;
if(i==B){
if(ap>bp){
bp=ap;
b=a;
}
}
else{
for(auto[j,_]:g[i]){
if(c[j]<=c[i]){
self(self,j);
}
}
}
ap--;
v[i]=0;
};
bt(bt,A);
b.resize(bp);
sort(b.begin(),b.end());
cout<<b.size()<<'\n';
for(int i:b){
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 | 293ms | 25084 KiB | ||||
subtask2 | 0/20 | ||||||
3 | Időlimit túllépés | 1.557s | 10576 KiB | ||||
4 | Időlimit túllépés | 1.587s | 41848 KiB | ||||
5 | Időlimit túllépés | 1.557s | 43288 KiB | ||||
6 | Elfogadva | 1.172s | 58300 KiB | ||||
7 | Időlimit túllépés | 1.549s | 50340 KiB | ||||
8 | Időlimit túllépés | 1.542s | 51072 KiB | ||||
9 | Időlimit túllépés | 1.542s | 81304 KiB | ||||
subtask3 | 0/15 | ||||||
10 | Időlimit túllépés | 1.549s | 66956 KiB | ||||
11 | Elfogadva | 9ms | 53524 KiB | ||||
12 | Időlimit túllépés | 1.6s | 51960 KiB | ||||
13 | Időlimit túllépés | 1.557s | 54940 KiB | ||||
14 | Időlimit túllépés | 1.554s | 60496 KiB | ||||
subtask4 | 0/20 | ||||||
15 | Időlimit túllépés | 1.544s | 68600 KiB | ||||
16 | Időlimit túllépés | 1.55s | 67236 KiB | ||||
17 | Időlimit túllépés | 1.565s | 56932 KiB | ||||
18 | Időlimit túllépés | 1.537s | 60556 KiB | ||||
19 | Hibás válasz | 1.287s | 60152 KiB | ||||
20 | Hibás válasz | 1.151s | 67548 KiB | ||||
subtask5 | 0/45 | ||||||
21 | Hibás válasz | 1.126s | 51960 KiB | ||||
22 | Időlimit túllépés | 1.559s | 98156 KiB | ||||
23 | Időlimit túllépés | 1.55s | 55748 KiB | ||||
24 | Időlimit túllépés | 1.583s | 67792 KiB | ||||
25 | Időlimit túllépés | 1.559s | 65716 KiB | ||||
26 | Időlimit túllépés | 1.567s | 73936 KiB | ||||
27 | Elfogadva | 237ms | 80772 KiB | ||||
28 | Időlimit túllépés | 1.565s | 89280 KiB | ||||
29 | Időlimit túllépés | 1.539s | 61836 KiB | ||||
30 | Időlimit túllépés | 1.572s | 83816 KiB | ||||
31 | Időlimit túllépés | 1.575s | 68896 KiB | ||||
32 | Időlimit túllépés | 1.575s | 57184 KiB | ||||
33 | Időlimit túllépés | 1.559s | 74892 KiB | ||||
34 | Időlimit túllépés | 1.569s | 77016 KiB | ||||
35 | Időlimit túllépés | 1.577s | 76744 KiB | ||||
36 | Időlimit túllépés | 1.565s | 73652 KiB | ||||
37 | Időlimit túllépés | 1.575s | 72468 KiB |