Pagini recente » Cod sursa (job #525580) | Cod sursa (job #2231730) | Cod sursa (job #2644016) | Cod sursa (job #806724) | Cod sursa (job #2419716)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("festivaluri.in");
ofstream fout("festivaluri.out");
const int NMAX = 101;
const int INF = 2000000000;
typedef pair < int, int > PII;
int N, M,P, V, K;
int mat[NMAX][NMAX];
int cost[NMAX][NMAX];
bool vis[NMAX];
int F[NMAX];
int dist[NMAX];
int v[NMAX];
void Read()
{
fin >> N >> M >> P >> V >> K;
int x, y, c;
for( int i = 1; i <= M; ++i )
{
fin >> x >> y >> c;
mat[x][y] = c;
mat[y][x] = c;
}
for( int i = 1; i <= K; ++i )
fin >> F[i];
/*for( int i = 1; i <= N; ++i )
{
fout << i << ' ';
for( int j = 1; j <= mat[i][0]; ++j )
fout << mat[i][j] << ' ';
fout << '\n';
}*/
for( int i = 1; i <= N; ++i )
dist[i] = INF;
for( int i = 1; i <= N; ++i )
if( mat[x][i] ) dist[i] = mat[x][i];
}
void Dijkstra( int x )
{
dist[x] = 0;
for( int i = 1; i <= N - 1; ++i )
{
int dmin = INF;
for( int j = 1; j <= N; ++j )
if( !vis[j] && dist[j] < dmin )
dmin = dist[j], x = j;
vis[x] = 1;
if( dmin != INF )
{
for( int j = 1; j <= N; ++j )
if( !vis[j] && dist[x] + mat[x][j] < dist[j] )
dist[j] = dist[x] + mat[x][j];
}
}
fout << dist[3] << ' ' << dist[5] << ' ';
for( int i = 1; i <= K; ++i )
v[++v[0]] = dist[F[i]];
sort( v + 1, v + v[0] + 1 );
int S = 0;
int ct = 0;
for( int i = 1; i <= v[0] && S < P ; ++i)
{
S += v[i];
if( S <= P )ct++;
}
fout << ct;
}
int main()
{
Read();
Dijkstra(V);
return 0;
}