城市问题（dijkstar）

本文主要是介绍城市问题（dijkstar），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• 城市问题
  Time Limit:10000MS  Memory Limit:65536K
  Total Submit:255 Accepted:95 
  Case Time Limit:1000MS 
  Description 
  　　设有n个城市，依次编号为0，1，2，……，n-1（n<=100），另外有一个文件保存n个城市之间的距离(每座城市之间的距离都小于等于1000)。当两城市之间的距离等于-1时，表示这两个城市没有直接连接。求指定城市k到每一个城市i（0<=I,k<=n-1）的最短距离。 
  Input 
  第一行有两个整数n和k，中间用空格隔开；以下是一个NxN的矩阵，表示城市间的距离，数据间用空格隔开。
  Output 
  输出指定城市k到各城市间的距离（从第0座城市开始，中间用空格分开）
  Sample Input 
  3 1
  0 3 1
  3 0 2
  1 2 0
  Sample Output 
  3 0 2
  Source 
  elba
  
  

• vari,j,k,n,m:longint;a:array[1..101,1..101]of longint;x,y:array[1..101]of longint;
  beginreadln(n,m);for i:=0 to n-1 dofor j:=0 to  n-1 doread(a[i,j]);for k:=0 to n-1 dofor i:=0 to n-1 dofor j:=0 to n-1 dobeginif (a[k,i]+a[k,j]<a[i,j]) and (a[k,i]<>-1) and (a[k,j]<>-1) then begina[i,j]:=a[k,i]+a[k,j];endend;for i:=0 to n-1 dowrite(a[n,i],' ')end.

var

  i,j,k,n,m,x,y,min,s,t:longint;
  a:array[-10..101,-10..101]of longint;
  b,c:array[-10..101]of longint;


begin
  readln(n,m);
  for i:=0 to n-1 do
    for j:=0 to n-1 do
      begin
        read(a[i,j]);
      end;
  for i:=0 to n-1 do
    c[i]:=a[m,i];
  for i:=0 to n-2 do
    begin
      min:=maxlongint;
      k:=0;
      for j:=0 to n-1 do
        begin
          if (a[k,i]<>-1) and (c[j]<min) then
            begin
              min:=c[j];
              k:=j;
            end;
        end;
      if k=0 then break;
      for j:=0 to n-1 do
        begin
          if c[k]+a[k,j]<c[j] then
            begin
              c[j]:=a[i,k]+c[k];
            end;
        end;
    end;
  for i:=0 to n-1 do
  begin
    write(c[i],' ');
  end;
end.

这篇关于城市问题（dijkstar）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---