9 – Laboratoriya ishi Mavzu: Bir uchdan boshqa uchlarga boradigan eng qisqa yo’llar m 1-Topshiriq

9 – Laboratoriya ishi
Mavzu: Bir uchdan boshqa uchlarga boradigan eng qisqa yo’llar M
1-Topshiriq
Given a connected weighted undirected graph.
Consider a pair of vertices, the distance between which is maximum among all pairs of vertices. The distance between them is called the diameter of the graph. Eccentricity of vertex v is the maximum distance from a vertex v to the other vertices of the graph. Radius of a graph is the smallest of the eccentricities of the vertices.
Find the diameter and radius of the graph.
Input
The first line of the input only number: N (1 ≤ N ≤ 100) - the number of vertices. The next N lines by N numbers - the adjacency matrix of the graph, where -1 means no edges between vertices, and any non-negative number - the presence of an edge weight. On the main diagonal of the matrix is always zero; weight edges do not exceed 1000.
Output
Output two numbers - the diameter and radius of the graph in separate lines.
Bog'langan vaznli yo'naltirilmagan grafik berilgan.
Barcha tepaliklar orasidagi masofa maksimal bo'lgan bir juft tepalikni ko'rib chiqing. Ularning orasidagi masofa grafaning diametri deb ataladi. V tepalikning ekssentrikligi - v tepalikdan grafaning boshqa tepalariga maksimal masofa. Grafik radiusi - tepaliklarning ekssentrikliklaridan eng kichigi.
Grafik diametri va radiusini toping.
Kiritish
Faqatgina kiritilgan birinchi satr soni: N (1 ≤ N-100) - tepalar soni. Keyingi N satrlari N raqamlari bilan - grafaning qo'shni matritsasi, bu erda -1 vertikallar o'rtasida qirralarning yo'qligi va har qanday manfiy bo'lmagan son - chekka vaznining mavjudligi. Matritsaning asosiy diagonalida har doim nol; og'irlik qirralari 1000 dan oshmaydi.
Chiqish
Ikkita raqamni chiqaring - grafaning diametri va radiusi alohida satrlarda.

№	Input	Output
1	4 0 -1 1 2 -1 0 -1 5 1 -1 0 4 2 5 4 0	8 5

#include
using namespace std;
long long d[1001][1001], n, i, j, k, MAX, m;
main()
{
cin >> n;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++){
cin >> d[i][j];
if(d[i][j] < 0) d[i][j] = 1e8;
}
for(k = 0; k < n; k++)
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
k = 1e8;
for(i = 0; i < n; i++){
m = 0;
for(j = 0; j < n; j++)
m = max(m, d[i][j]);
k = min(k, m);
MAX = max(MAX, m);
}
cout << MAX << endl << k;
}