Cerința

N orașe sunt conectate între ele prin M autostrăzi bidirecționale, fiecare autostradă (a, b) având un cost de tranzit c atașat. Se dorește revizuirea sistemului de taxare, însă sunt câteva aspecte ce trebuie luate în calcul și necesită investigație, deoarece o parte dintre cele N orașe sunt centre comerciale sau turistice importante.

Se dorește să se afle răspunsul la o serie de Q întrebări de forma: (X, T) – câte dintre celelalte N-1 orașe au acces către orașul X, cu o taxă totală de cel mult T către fiecare oraș?

Date de intrare

Fișierul de intrare tollroads.in conține pe primul rând numerele N, M și Q reprezentând numărul de orașe, numărul de autostrăzi și numărul de interogări. Pe fiecare din următoarele M rânduri sunt scrise câte trei numere a, b, c, separate prin câte un spațiu, reprezentând două orașe între care există o autostradă și costul autostrăzii. Pe următoarele Q rânduri se află scrise câte două numere X și T, separate prin spațiu, reprezentând datele interogărilor, conform enunțului.

Date de ieșire

În fișierul de ieșire tollroads.out se vor scrie pe fiecare dintre primele Q rânduri câte un singur număr, reprezentând răspunsurile la interogări, în ordinea în care ele au fost puse.

Restricții și precizări

1 ≤ N ≤ 100.000
1 ≤ M ≤ 100.000
1 ≤ a, b ≤ N
1 ≤ c ≤ 100.000
1 ≤ T ≤ 100.000
1 ≤ Q ≤ 100
între orice două orașe poate exista mai mult de o autostrada

Exemplu

tollroads.in

tollroads.out

Explicație

Orașele 2,3,4,5,6,7 au acces către orașul 1 cu taxă maximă 6
Orașele 2,3,4,5,6 au acces către orașul 1 cu taxă maximă 5
Orașele 2,3,5 au acces către orașul 1 cu taxă maximă 4
Orașele 1,3,5 au acces către orașul 2 cu taxă maximă 3
Orașele 2,3,5,6,7 au acces către orașul 4 cu taxă maximă 4

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 TollRoads:

#include<bits/stdc++.h>

#define maxN 100002
#define maxQ 102

using namespace std;

FILE *fin = freopen("tollroads.in", "r", stdin);
FILE *fout = freopen("tollroads.out", "w", stdout);

struct Edge
{
    int u, c;
};

vector < Edge > Adj[maxN];
int d[maxN],n,q;
vector < int > h, H[maxN];
bitset < maxN > inQ;

int Dijkstra(int u, int Time)
{
    int cnt = 0;
    for (int i = 1; i <= n; ++ i)
        if (i == u)
        {
            inQ[i] = 1;
            d[i] = 0;
            H[0].push_back(i);
        }
        else
        {
            inQ[i] = 0;
            d[i] = maxN;
        }
    for (int t = 0; t <= Time; ++ t)
    {
        for (int nod : H[t])
        {
            if (d[nod] != t) continue;
            ++ cnt;
            for (Edge e : Adj[nod])
            {
                int v = e.u;
                if (t + e.c <= Time && d[v] > t + e.c)
                {
                    d[v] = t + e.c;
                    if (!inQ[v])
                    {
                        h.push_back(v);
                        inQ[v] = 1;
                    }
                }
            }
        }
        H[t].clear();
        while (!h.empty())
        {
            int v = h.back();
            inQ[v] = 0;
            h.pop_back();
            if (d[v] <= Time)
                H[d[v]].push_back(v);
        }
    }
    return cnt;
}

int main()
{
    int m;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 0; i < m; ++ i)
    {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        Adj[u].push_back(Edge{v, c});
        Adj[v].push_back(Edge{u, c});
    }
    for (int i = 0; i < q; ++ i)
    {
        int u, t;
        scanf("%d%d", &u, &t);
        printf("%d\n", Dijkstra(u, t) - 1);
    }
    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 #2933 TollRoads

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2933 TollRoads 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 #2933 TollRoads