圖的最短路徑

一、任意兩點之間的最短距離已知下圖中給定的關(guān)系，求出圖中任意給定兩點之間的最短距離輸入：56151223131715492352413457輸出：42二、主席的居住城市distp.pas/dist.in/dist.out【問題描述】OI國共有n個城市，任意兩個城市都直接或間接連通，每兩個直接相連的城市之間都有一雙向公路。OI國的CHEN主席要選擇其中一個城市居住，由于他到每個城市考察的概率是相等的，所以他選擇的城市到其它所有城市的的最短距離的和應(yīng)該最小?，F(xiàn)在，給出城市間的道路，請幫助CHEN主席確定居住的城市。【輸入數(shù)據(jù)：】Nn*n的矩陣，(i,j)表示i到j(luò)之間的距離(i,j)=(j,i)(i,j)=-1表示

i,j之間沒有直接道路。【輸出數(shù)據(jù)：】城市編號（如果有多個城市同時最小，輸出編號最小的城市）最小距離和【輸入樣例：】5-131-172-131-130-170-130-176-172-176-140-170-140-1【輸出樣例】2234說明：數(shù)據(jù)規(guī)模：n<=100(i,j)<=100三、路徑減半給定一個n（<100）個結(jié)點的帶權(quán)圖，可將任一條邊減半，問減哪條邊可以使從給定點A到給定點B的最短路徑長度下降的最多。如下圖，1到5的最短路徑1—>3-5,最短距離：2+8=10。其中，3到5之間的距離減半變成4后，1到5的最短距離變?yōu)?，下降的最多。輸入：第一行：n，A，B（<100）.中間一個空格隔開。以下n行是n*n的矩陣a[I,j]，圖的權(quán)值。A[I,j]=-1表示i與j之間無邊、或者i=j，其他均為小于1000的正整數(shù)。輸出：選擇合適的邊減半后，A到B的最短距離下降的值（小數(shù)點后保留1位小數(shù)）。樣例：輸入：515-1627-16-1-1-182-1-1-187-1-1-16-1886-1輸出：4.0四、上學(xué)路線【問題描述】小A經(jīng)過初三一年的努力，終于考上了認(rèn)為適合自己的山師附中。由于小A的家離學(xué)校很遠(yuǎn)，他又懶得騎自行車上學(xué)，于是他決定開學(xué)之前先考察一下上學(xué)路上的公交車路線，然后做出合適的選擇，為新學(xué)期做好第一個準(zhǔn)備。經(jīng)過幾天的考察，小A記下了若干路公共汽車路線，這些公共汽車都是從某個站出發(fā)，沿途依次經(jīng)過很多的中間站，最后到達(dá)終點站，并且都是單向的路線。令小A感到非常不爽的是，他很難找到有一趟公共汽車能從他家直達(dá)學(xué)校，大部分是他需要先乘某一路汽車坐上幾站，下來后再換乘同一站臺的另一路汽車,這樣換乘幾次后才能到達(dá)學(xué)校。幸運的是他的家門口和學(xué)校門口都一個汽車站。小A坐車最煩的就是等車，于是他決定選擇一個換乘汽車次數(shù)最少的上學(xué)路線?，F(xiàn)在用整數(shù)1,2,...,n給所有的公共汽車站編號，約定小A的家門口的汽車站編號為1，學(xué)校門口的汽車站的編號為n。你的任務(wù)是：幫助小A尋找一個最優(yōu)乘車方案,使他從家乘車到學(xué)校的過程中換車的次數(shù)最少?！据斎搿康谝恍蠱，表示M條單程公共汽車線路。第二行N，表示總共有N個車站。以下M行依次給出了第1條到第M條汽車線路的信息。其中第i行給出的是第i條線路的信息，從左至右按運行順序依次給出了該線路上的所有站號，相鄰兩個站號之間用一個空格隔開。【輸出】一行。如果無法乘從家到學(xué)校，則輸出"NoRoud!"，否則輸出你的程序所找到的最少換車次數(shù)，換車次數(shù)為0表示不需換車即可到直達(dá)·【輸入輸出樣例】roud.inroud.out3767473612352【輸入輸出樣例解釋】乘車路線：