Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Ștefan Șindilar
- #include <bits/stdc++.h>
- #define NMAX 1e2
- using namespace std;
- ifstream fin("drumuri.in");
- ifstream f("orase.in");
- ofstream fout("date.out");
- int n;
- char orase[256][256];
- vector < vector < int > > G(NMAX, vector < int >(NMAX));
- vector < int > dist(NMAX, INT_MAX);
- vector < bool > visited(NMAX, false);
- void Read()
- {
- fin >> n;
- int x, y, c;
- while(!fin.eof())
- {
- fin >> x >> y >> c;
- G[x][y] = G[y][x] = c;
- }
- fin.close();
- int i = 1;
- for(; i <= n; ++i)
- f >> orase[i];
- f.close();
- }
- int MinDistance()
- {
- int minn = INT_MAX, min_index, i = 1;
- for(; i <= n; ++i)
- if(visited[i] == false && dist[i] <= minn)
- {
- minn = dist[i];
- min_index = i;
- }
- return min_index;
- }
- void Print()
- {
- int i = 1;
- for(; i <= n; ++i)
- {
- fout << " " << orase[i];
- int j = 1;
- for(; j <= 30 - strlen(orase[i]); ++j)
- fout << " ";
- fout << dist[i] << endl;
- }
- }
- void Dijkstra(int node)
- {
- dist[node] = 0;
- int i = 1;
- for(; i < n; ++i)
- {
- int p = MinDistance();
- visited[p] = true;
- int j = 1;
- for(; j <= n; j++)
- if(!visited[j] && G[p][j] && dist[p] != INT_MAX
- && dist[p] + G[p][j] < dist[j])
- dist[j] = dist[p] + G[p][j];
- }
- fout << "Din " << orase[node] << endl;
- Print();
- }
- int main()
- {
- Read();
- int x;
- cout << "Nr orasului de plecare: ";
- cin >> x;
- Dijkstra(x);
- return 0;
- }
- Radauti
- Suceava
- Milisauti
- Vicovu_de_Sus
- Gura_Humorului
- Vatra_Dornei
- Siret
- Campulung_Moldovenesc
- Cajvana
- Solca
- Falticeni
- 11
- 2 3 27
- 3 1 10
- 1 7 19
- 2 7 43
- 2 9 31
- 3 9 13
- 3 10 17
- 2 5 35
- 10 5 29
- 5 8 32
- 8 6 43
- 1 4 23
- 1 5 45
- 1 8 75
- 5 11 36
- 2 11 43
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement