10134 | 2024. 03. 27 21:10:07 | 111 | Vázsony vonatjegyet vásárol | cpp17 | Elfogadva 100/100 | 860ms | 179800 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
struct DSU {
vector<int> v;
DSU(int n) : v(n + 1, -1) {
}
int find(int a) {
return v[a] < 0 ? a : v[a] = find(v[a]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) {
return;
}
if (v[a] > v[b]) {
swap(a, b);
}
v[a] += v[b];
v[b] = a;
}
};
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);
DSU dsu(N+1);
auto dfs1=[&](auto self,int i)->void{
if(v[i]){
return;
}
v[i]=1;
for(auto[j,_]:g[i]){
if(c[j]==c[i]){
dsu.unite(i,j);
}
if(c[j]<=c[i]){
self(self,j);
}
}
};
dfs1(dfs1,A);
vector<set<int>>gg(N+1);
for(int i=1;i<=N;i++){
for(auto[j,_]:g[i]){
if(c[j]<=c[i]&&dsu.find(j)!=dsu.find(i)){
gg[dsu.find(i)].insert(dsu.find(j));
}
}
}
vector<int>w(N+1),u(N+1);
auto dfs2=[&](auto self,int i)->void{
if(w[i]){
return;
}
int x=0;
for(int j:gg[i]){
self(self,j);
if(w[j]>x){
x=w[j];
u[i]=j;
}
}
w[i]=-dsu.v[dsu.find(i)]+x;
};
dfs2(dfs2,dsu.find(A));
vector<int>y(N+1);
for(int i=dsu.find(A);i;i=u[i]){
y[i]=1;
}
cout<<w[dsu.find(A)]<<'\n';
for(int i=1;i<=N;i++){
if(y[dsu.find(i)]){
cout<<i<<' ';
}
}
cout<<'\n';
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1888 KiB | ||||
2 | Elfogadva | 140ms | 38324 KiB | ||||
subtask2 | 20/20 | ||||||
3 | Elfogadva | 59ms | 20260 KiB | ||||
4 | Elfogadva | 435ms | 104180 KiB | ||||
5 | Elfogadva | 298ms | 81328 KiB | ||||
6 | Elfogadva | 238ms | 69564 KiB | ||||
7 | Elfogadva | 324ms | 81628 KiB | ||||
8 | Elfogadva | 233ms | 65344 KiB | ||||
9 | Elfogadva | 546ms | 135100 KiB | ||||
subtask3 | 15/15 | ||||||
10 | Elfogadva | 160ms | 36220 KiB | ||||
11 | Elfogadva | 13ms | 6640 KiB | ||||
12 | Elfogadva | 12ms | 5688 KiB | ||||
13 | Elfogadva | 35ms | 11456 KiB | ||||
14 | Elfogadva | 93ms | 32560 KiB | ||||
subtask4 | 20/20 | ||||||
15 | Elfogadva | 71ms | 34776 KiB | ||||
16 | Elfogadva | 243ms | 60076 KiB | ||||
17 | Elfogadva | 41ms | 27876 KiB | ||||
18 | Elfogadva | 83ms | 42208 KiB | ||||
19 | Elfogadva | 37ms | 21468 KiB | ||||
20 | Elfogadva | 82ms | 37584 KiB | ||||
subtask5 | 45/45 | ||||||
21 | Elfogadva | 3ms | 4684 KiB | ||||
22 | Elfogadva | 860ms | 179800 KiB | ||||
23 | Elfogadva | 52ms | 20236 KiB | ||||
24 | Elfogadva | 230ms | 64708 KiB | ||||
25 | Elfogadva | 199ms | 58424 KiB | ||||
26 | Elfogadva | 368ms | 88708 KiB | ||||
27 | Elfogadva | 187ms | 57852 KiB | ||||
28 | Elfogadva | 642ms | 143300 KiB | ||||
29 | Elfogadva | 137ms | 40356 KiB | ||||
30 | Elfogadva | 646ms | 119888 KiB | ||||
31 | Elfogadva | 224ms | 74332 KiB | ||||
32 | Elfogadva | 48ms | 15452 KiB | ||||
33 | Elfogadva | 323ms | 84840 KiB | ||||
34 | Elfogadva | 264ms | 77516 KiB | ||||
35 | Elfogadva | 294ms | 72804 KiB | ||||
36 | Elfogadva | 259ms | 63140 KiB | ||||
37 | Elfogadva | 256ms | 59008 KiB |