Pagini recente » Cod sursa (job #2468448) | Cod sursa (job #1700392) | Cod sursa (job #2261942) | Cod sursa (job #1422049) | Cod sursa (job #2039821)
#include <cstdio>
#include <vector>
#include <climits>
using namespace std;
const int nmax=3e5+3;
long long t,n,m,s,d,k,a,b,timp,v[nmax][4],nr,c;
long long dist[nmax],suma;
vector <int> sol;
void init()
{
for(int i=1;i<=n;++i) dist[i]=INT_MAX;
dist[d]=0;
}
void read()
{
scanf("%d%d%d%d",&n,&m,&s,&d);
init();
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&v[i][1],&v[i][2],&v[i][3]);
if(v[i][1]==d) dist[v[i][2]]=v[i][3];
if(v[i][2]==d) dist[v[i][1]]=v[i][3];
}
scanf("%d",&k);
for(int i=1;i<=k;++i)
{
scanf("%d",&a);
suma+=v[a][3];
}
}
void dijkstra()
{
bool ok=1;
while(ok&&nr<n)
{
ok=0;
for(int i=1;i<=m;++i)
{
a=v[i][1];
b=v[i][2];
c=v[i][3];
if(dist[a]>dist[b]+c)
{
dist[a]=dist[b]+c;
ok=1;
}
if(dist[b]>dist[a]+c)
{
dist[b]=dist[a]+c;
ok=1;
}
}
++nr;
}
}
void solve()
{
for(int i=1;i<=n;++i)
{
if(dist[i]<=suma) sol.push_back(i);
}
printf("%d\n",sol.size());
for(int i=0;i<sol.size();++i) printf("%d ",sol[i]);
printf("\n");
}
int main()
{
freopen("tempest.in","r",stdin);
freopen("tempest.out","w",stdout);
scanf("%d",&t);
while(t--)
{
suma=nr=0;
read();
sol.clear();
dijkstra();
solve();
}
return 0;
}