Primăria din Iași a hotărât să modernizeze șoselele din localitate. O șosea este o porțiune de drum care unește două intersecții. Firma constructoare a făcut un studiu pentru a determina costurile pentru fiecare șosea. Fondurile sunt limitate, astfel că în prima fază vor fi modernizate doar drumurile din apropierea Palas-ului, care se află la intersecția cu numărul 1. Mai precis: orice șosea modernizată trebuie sa fie cel puțin la fel de aproape de Palas ca orice șosea ce nu va fi modernizată.

Lungimea drumului dintre două intersecții a și b este numărul cel mai mic de intersecții ce trebuie parcurse pentru a ajunge de la a la b. Șoseaua (a, b) este mai aproape de Palas față de șoseaua (c, d) dacă lungimea drumului de la Palas până la cea mai apropiată intersecție dintre a și b este mai mică decât până la cea mai apropiată intersecție dintre c și d. Dacă lungimile drumurilor până la cele mai apropiate intersecții sunt egale, se compară lungimile drumurilor până la celelalte două intersecții. De exemplu dacă pentru șoselele (4, 7) și (3, 5) avem distanțele de la Palas până la intersecțiile: 3, 4, 5, 7 egale cu: 10, 10, 10, 11 în această ordine, atunci (3, 5) e mai aproape de Palas față de (4, 7) deoarece distanțele minime sunt ambele egale cu 10 dar distanța până la intersecția 3 este tot 10, mai mică față de distanța până la intersecția 7 care este 11. Dacă nu există cale de acces de la Palas la o intersecție a atunci șoselele legate de a nu vor fi modernizate.

Cerința

Cunoscând: N – numărul de intersecții din oraș codificate prin numere naturale din mulțimea 1..N, M – numărul de șosele și șoselele împreună cu costul de modernizare, și F – fondurile de care dispune primăria, să se afle K – numărul maxim de șosele care pot fi modernizate.

Date de intrare

În fișierul de intrare modernizare.in se află pe prima linie N, M şi F reprezentând numărul de intersecții, numărul de șosele şi respectiv fondurile totale F. Următoarele M linii conțin triplete de numere naturale a b c, unde (a, b) reprezintă șoseaua ce leagă intersecțiile a și b, iar c este costul de modernizare. Pentru orice linie (a, b) avem: a ≠ b și nu mai există o altă linie cu (a, b) sau (b, a).

Date de ieșire

În fișierul de ieșire modernizare.out se va afla pe prima linie un singur număr natural K, reprezentând numărul maxim de șosele care pot fi modernizate conform restricțiilor.

Restricții și precizări

1 ≤ N, M ≤ 100000
1 ≤ a, b ≤ N
1 ≤ F, c ≤ 2.000.000.000
N ≤ 1000, pentru teste în valoare de 50 puncte.
În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplul din enunț.

Exemplu

modernizare.in

modernizare.out

Explicație

Șoselele (1,2) și (1,3) sunt cele mai aproape de intersecția 1. Șoseaua (2,3) este mai aproape de Palas față de (2,4) și (3,4) deoarece ambele capete sunt mai aproape de 1. Se modernizează cele trei șosele.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema modernizare:

#include <bits/stdc++.h>
#define NMAX 100005
#define pii pair<int,int>
using namespace std;

ifstream f("modernizare.in");
ofstream g("modernizare.out");

int n, m, F, x, y, c, lg[NMAX];
vector<int> v[NMAX];
queue<int> Q;
set<pii> S;

struct muchie{
    int x,y,c;
};
vector<muchie> M;

bool comp(muchie a, muchie b){
    if (min(lg[a.x],lg[a.y]) == min(lg[b.x],lg[b.y])){
        if (max(lg[a.x],lg[a.y]) == max(lg[b.x],lg[b.y]))
            return a.c < b.c;
        return max(lg[a.x],lg[a.y]) < max(lg[b.x],lg[b.y]);
    }
    return min(lg[a.x],lg[a.y]) < min(lg[b.x],lg[b.y]);
}

int main()
{
    f >> n >> m >> F;
    assert(1 <= n && n <= 1e5);
    assert(1 <= m && m <= 1e5);
    assert(1 <= F && F <= 2e9);

    for (int i=1;i<=m;i++){
        f >> x >> y >> c;
        assert(1 <= x && x <= n);
        assert(1 <= y && y <= n);
        assert(1 <= c && c <= 2e9);
        assert(S.find({x,y}) == S.end());
        assert(x != y);
        S.insert({x,y}); S.insert({y,x});

        v[x].push_back(y);
        v[y].push_back(x);
        M.push_back({x,y,c});
    }

    Q.push(1);
    memset(lg,0x3f,sizeof(lg));
    lg[1] = 1;
    while (!Q.empty()){
        int nod = Q.front();
        Q.pop();
        for (auto it : v[nod]){
            if (lg[it] > 1e9){
                lg[it] = lg[nod] + 1;
                Q.push(it);
            }
        }
    }

    sort(M.begin(),M.end(),comp);

    int k = 0;
    for (int i=0;i < M.size() && lg[M[i].x] < 1e9 && M[i].c <= F;i++,k++)
        F -= M[i].c;

    g << k << '\n';


    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2893 modernizare

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2893 modernizare de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2893 modernizare