если в двух словах то нужно проверить, что матрица правильно задает минимальный путь между вершинами ...
ACM ICPC 20062007, NEERC, Moscow Subregional Contest
Moscow, October 21, 2006
Problem E. Existence of a Graph
Time limit:
1 second
Memory limit:
64 MiB
Let G be a weighted undirected graph with N vertices and M edges. The edge weights are positive integers.
The length of a path P in G is defined to be the sum of weights of edges on P. The length of a shortest path
in G from vi to v j is called the distance from vi to v j and is denoted by di j (for i, j = 1, 2, . . . , N). If no such
path exist, we put di j = -1
The distance matrix of a graph with N nodes is an N Ч N matrix M containing the values di j. In case di j =
the correspoding element of M is set to -1. For example, the distance matrix for the graph depicted in
Figure 1 is
0 1 2 -1
1 0 1 -1
2 1 0 -1
-1 -1 -1
0
You are given a square matrix D with integer elements. Write a program to determine if D is the distance
matrix of some graph.
Input
The input has the structure as follows. The first line contains an integer N (1 N 200). The next N lines
describe a matrix D. Each line contains N integers from range [-1, 1 000] separated by spaces.
Output
If the given matrix is a distance matrix of a certain undirected graph, print YES, otherwise print NO.
Example
stdin
stdout
4
YES
0 1 2 -1
1 0 1 -1
2 1 0 -1
-1 -1 -1 0
3
NO
0 1 3
1 0 1
3 1 0
верна ли гипотеза, что матрица минимальных расстояний между вершинами неориетированого графа верна тогда и только тогда, когда для любых вершин а и б, не существует такой вершины с, что путь а с б будет короче чем а б
в смысле как можно ее доказать теоретически?
я исползовал для решения грубый алгоритм с кубическим временем выполнения:
//#include <stdio.h>
#include <gtk/gtk.h>
int main () {
int d,i,ii,iii;
int a,b,c;
scanf("%d",&d);
int **matrix;
//matrix = (int**) new int [d][d];
matrix = g_new( int *,d);
for ( i=0;i<d;i++)
{
matrix[i] = g_new( int,d);
for (ii=0;ii<d;ii++)
{
scanf("%d",&matrix[i][ii]) ;
}
}
for ( i=0;i<d;i++)
{
a=matrix[i][i];
if ( a ) {
g_print(" found wrong edge at %d - %d (%d) \n",i,i,a);
return 1;
}
for (ii=0;ii<d;ii++)
{
a=matrix[i][ii];
b=matrix[ii][i];
if (a !=b ) {
g_print(" found directed edge at %d - %d \n (%d != %d \n",i,ii,a,b);
return 1;
}
for (iii=0;iii<d;iii++)
{
b=matrix[i][iii];
c=matrix[iii][ii];
// g_print("%d\t%d\t%d\n ",a,b,c);
if ((a>b+c) &&( b>0) &&( c>0) ) {
g_print(" wrong edges at %d - %d, over %d \n (%d > %d + %d)\n",i,ii,iii,a,b,c);
return 1;
}
}
}
}
g_print("YES\n");
return 0;
}
существуют ли более оптимизированые алгоритмы для поиска ошибок в матрице?
