10132 | 2024-03-27 20:18:50 | 111 | Vázsony vonatjegyet vásárol | cpp17 | Időlimit túllépés 0/100 | 1.6s | 75456 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;
vector<int>v(M);
auto bt=[&](auto self,int i)->void{
a.push_back(i);
if(i==B){
vector<int>aa(a);
sort(aa.begin(),aa.end());
aa.erase(unique(aa.begin(),aa.end()),aa.end());
if(aa.size()>ans.size()){
ans=aa;
}
}
else{
for(auto[j,_,k]:g[i]){
if(v[k]>=2){
continue;
}
v[k]++;
if(c[j]<=c[i]){
self(self,j);
}
v[k]--;
}
}
a.pop_back();
};
bt(bt,A);
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 | 1832 KiB | ||||
2 | Időlimit túllépés | 1.6s | 16232 KiB | ||||
subtask2 | 0/20 | ||||||
3 | Időlimit túllépés | 1.557s | 8280 KiB | ||||
4 | Időlimit túllépés | 1.58s | 41552 KiB | ||||
5 | Időlimit túllépés | 1.575s | 33192 KiB | ||||
6 | Időlimit túllépés | 1.542s | 24876 KiB | ||||
7 | Időlimit túllépés | 1.569s | 32628 KiB | ||||
8 | Időlimit túllépés | 1.557s | 25180 KiB | ||||
9 | Időlimit túllépés | 1.574s | 53492 KiB | ||||
subtask3 | 0/15 | ||||||
10 | Időlimit túllépés | 1.567s | 31888 KiB | ||||
11 | Elfogadva | 9ms | 6352 KiB | ||||
12 | Időlimit túllépés | 1.552s | 4900 KiB | ||||
13 | Időlimit túllépés | 1.567s | 9976 KiB | ||||
14 | Időlimit túllépés | 1.55s | 18136 KiB | ||||
subtask4 | 0/20 | ||||||
15 | Időlimit túllépés | 1.57s | 15260 KiB | ||||
16 | Időlimit túllépés | 1.587s | 22772 KiB | ||||
17 | Időlimit túllépés | 1.574s | 10964 KiB | ||||
18 | Időlimit túllépés | 1.557s | 14352 KiB | ||||
19 | Időlimit túllépés | 1.57s | 7628 KiB | ||||
20 | Időlimit túllépés | 1.55s | 12680 KiB | ||||
subtask5 | 0/45 | ||||||
21 | Időlimit túllépés | 1.554s | 4568 KiB | ||||
22 | Időlimit túllépés | 1.575s | 75456 KiB | ||||
23 | Időlimit túllépés | 1.562s | 10524 KiB | ||||
24 | Időlimit túllépés | 1.555s | 28192 KiB | ||||
25 | Időlimit túllépés | 1.559s | 24560 KiB | ||||
26 | Időlimit túllépés | 1.552s | 35396 KiB | ||||
27 | Elfogadva | 609ms | 45008 KiB | ||||
28 | Időlimit túllépés | 1.569s | 60936 KiB | ||||
29 | Időlimit túllépés | 1.564s | 18368 KiB | ||||
30 | Időlimit túllépés | 1.531s | 51332 KiB | ||||
31 | Időlimit túllépés | 1.559s | 24432 KiB | ||||
32 | Időlimit túllépés | 1.582s | 12024 KiB | ||||
33 | Időlimit túllépés | 1.575s | 33556 KiB | ||||
34 | Időlimit túllépés | 1.578s | 30228 KiB | ||||
35 | Időlimit túllépés | 1.562s | 30220 KiB | ||||
36 | Időlimit túllépés | 1.57s | 30320 KiB | ||||
37 | Időlimit túllépés | 1.554s | 30280 KiB |