Cod sursa(job #2419716)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 9 mai 2019 12:02:22
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#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;
}