10131 | 2024-03-27 20:12:49 | 111 | Vázsony vonatjegyet vásárol | cpp17 | Hibás válasz 0/100 | 1.583s | 50980 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++>50000000){
return;
}
if(v[i]){
return;
}
v[i]=1;
a[ap++]=i;
if(i==B){
if(ap>bp){
bp=ap;
memcpy(b.data(),a.data(),ap*sizeof(int));
}
}
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 | 279ms | 22176 KiB | ||||
subtask2 | 0/20 | ||||||
3 | Időlimit túllépés | 1.554s | 6400 KiB | ||||
4 | Időlimit túllépés | 1.552s | 28788 KiB | ||||
5 | Időlimit túllépés | 1.567s | 22920 KiB | ||||
6 | Elfogadva | 1.141s | 37988 KiB | ||||
7 | Időlimit túllépés | 1.574s | 23152 KiB | ||||
8 | Időlimit túllépés | 1.583s | 19096 KiB | ||||
9 | Időlimit túllépés | 1.569s | 37956 KiB | ||||
subtask3 | 0/15 | ||||||
10 | Időlimit túllépés | 1.575s | 19164 KiB | ||||
11 | Elfogadva | 9ms | 5488 KiB | ||||
12 | Hibás válasz | 1.08s | 5816 KiB | ||||
13 | Hibás válasz | 1.179s | 11840 KiB | ||||
14 | Időlimit túllépés | 1.567s | 12660 KiB | ||||
subtask4 | 0/20 | ||||||
15 | Hibás válasz | 760ms | 20848 KiB | ||||
16 | Időlimit túllépés | 1.557s | 19484 KiB | ||||
17 | Hibás válasz | 1.25s | 15952 KiB | ||||
18 | Hibás válasz | 1.202s | 23228 KiB | ||||
19 | Hibás válasz | 656ms | 12420 KiB | ||||
20 | Hibás válasz | 589ms | 20036 KiB | ||||
subtask5 | 0/45 | ||||||
21 | Hibás válasz | 555ms | 4776 KiB | ||||
22 | Időlimit túllépés | 1.55s | 50980 KiB | ||||
23 | Időlimit túllépés | 1.557s | 8212 KiB | ||||
24 | Időlimit túllépés | 1.554s | 20232 KiB | ||||
25 | Időlimit túllépés | 1.57s | 18036 KiB | ||||
26 | Időlimit túllépés | 1.562s | 26212 KiB | ||||
27 | Elfogadva | 217ms | 32708 KiB | ||||
28 | Időlimit túllépés | 1.575s | 41004 KiB | ||||
29 | Időlimit túllépés | 1.547s | 13592 KiB | ||||
30 | Időlimit túllépés | 1.569s | 35768 KiB | ||||
31 | Időlimit túllépés | 1.57s | 20984 KiB | ||||
32 | Időlimit túllépés | 1.547s | 8720 KiB | ||||
33 | Időlimit túllépés | 1.575s | 26580 KiB | ||||
34 | Időlimit túllépés | 1.565s | 32924 KiB | ||||
35 | Időlimit túllépés | 1.569s | 28672 KiB | ||||
36 | Időlimit túllépés | 1.565s | 25424 KiB | ||||
37 | Időlimit túllépés | 1.567s | 24236 KiB |