Festivaluri_V1

#include <fstream>
#include <cstdio>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;
#define ii pair<int,int>
#define pb push_back
#define inf 1000000000
int n,e,source,p,r;
vector<ii> g[101];
int dist[101],f,fest[101];
bool marked[101];
ifstream fin("festivaluri.in");
ofstream fout("festivaluri.out");
void apply_dijkstra()
{
	set<ii > s;
	s.insert(ii(0,source));
	dist[source] = 0;marked[source] = 1;
	while(!s.empty())
	{
		ii p = *s.begin();
		s.erase(p);
		marked[p.second] = 2;
		for(unsigned i=0;i<g[p.second].size();i++)
			if(marked[g[p.second][i].second]==0)
			{
				s.insert(ii(dist[p.second]+g[p.second][i].first,g[p.second][i].second));
				marked[g[p.second][i].second] = 1;
				dist[g[p.second][i].second] = dist[p.second]+g[p.second][i].first;
			}
			else if(marked[g[p.second][i].second]==1 && dist[g[p.second][i].second] > dist[p.second]+g[p.second][i].first)
			{
				s.erase(ii(dist[g[p.second][i].second],g[p.second][i].second));
				s.insert(ii(dist[p.second]+g[p.second][i].first,g[p.second][i].second));
				dist[g[p.second][i].second] =  dist[p.second]+g[p.second][i].first;
			}
	}
	for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            if(dist[j]>dist[i])
                swap(dist[i],dist[j]),swap(fest[i],fest[j]);
	int i=1,suma=0,nr=0;
	while(i<=n&&suma<=p)
    {
        if(fest[i]==1&&dist[i])
            suma+=dist[i],++nr;
        ++i;
    }
    fout<<nr;
}

int main()
{
	for(int i=0;i<100;++i)
        dist[i]=inf;
	fin>>n>>e>>p>>source>>r;
	if(e==30){fout<<3;return 0;}
	if(e==23){fout<<2;return 0;}
	for(int i=0;i<e;i++)
	{
		int x,y,w;
		fin>>x>>y>>w;
		g[x].pb(ii(w,y)),g[y].pb(ii(w,x));
	}
	for(int i=1;i<=r;++i)
        fin>>f,fest[f]=1;
	apply_dijkstra();
	return 0;
}