廉價(jià)最短路徑

題目大意：

一個(gè)圖中，在滿足最短路的前提下，求最小代價(jià)

原題：

題目描述

圖是由一組頂點(diǎn)和一組邊組成的。一條邊連接兩個(gè)頂點(diǎn)。例如，圖1表示了一個(gè)有4個(gè)頂點(diǎn)V、5條邊的圖。圖中，每條邊e是有方向的，方向從起點(diǎn)到終點(diǎn)，并且每條邊都有價(jià)值。用整數(shù)0,1,…,m-1可以表示一個(gè)有m個(gè)頂點(diǎn)的圖。

一條路徑連接了一個(gè)點(diǎn)Vi和另一個(gè)點(diǎn)Vj，其方向與經(jīng)過(guò)的一系列邊的方向一致。路徑的長(zhǎng)度是途經(jīng)邊的條數(shù)，路徑的費(fèi)用是邊價(jià)值的總和。對(duì)于一個(gè)給定的圖，你的任務(wù)是在所有最短路徑中，找出需要最少費(fèi)用的連接V0和V1的路徑。一個(gè)需要最少費(fèi)用的最短路徑稱之為廉價(jià)最短路徑。
讓我們重新考慮圖1，從0到1的最短路徑是只含一條邊的路徑0→1，費(fèi)用是10。當(dāng)然，還有更便宜的路：0→2→1和 0→3→1，但是它們比第一條路徑長(zhǎng)(有2條邊)。所以，0→1是廉價(jià)最短路徑。
看一下另一個(gè)例子，圖2，它有2條最短路徑，其長(zhǎng)度是2，路徑0→3→1(費(fèi)用=4)比路徑0→2→1(費(fèi)用=5)花費(fèi)少。還用另一條路徑0→2→3→1(費(fèi)用=3)，雖然便宜但是很長(zhǎng)。所以，廉價(jià)最短路徑是0→3→1。

輸入

輸入文件第一行有兩個(gè)整數(shù)m和n，用一個(gè)空格隔開，其中，m是頂點(diǎn)數(shù)，而n是邊數(shù)。接下來(lái)的n行給出所有的邊及其價(jià)值，每行有3個(gè)整數(shù)(相鄰兩個(gè)整數(shù)間有一個(gè)空格)，表示起點(diǎn)，終點(diǎn)和邊的價(jià)值。頂點(diǎn)最多有100個(gè)，編號(hào)在0到99之間。邊最多有1000條，其價(jià)值在0到2^15-1之間。

輸出

輸出文件僅有一行包含一個(gè)整數(shù)，即V0→V1的廉價(jià)最短路徑的費(fèi)用。當(dāng)出現(xiàn)有多個(gè)廉價(jià)最短路徑的情況時(shí)，它們的費(fèi)用是一樣的。

輸入樣例

4 5 0 2 2 0 3 2 0 1 10 2 1 2 3 1 2

輸出樣例

10

說(shuō)明

東莞市2013年信息學(xué)特長(zhǎng)生測(cè)試題第四題

解題思路：

數(shù)據(jù)很小，直接Floyed就可以了

代碼：

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,m,x,y,z,a[105][105],c[105][105]; int main() {scanf("%d %d",&n,&m);memset(a,127/3,sizeof(a));memset(c,127/3,sizeof(c));for (int i=1;i<=m;++i){scanf("%d %d %d",&x,&y,&z);a[x][y]=z;c[x][y]=1;//預(yù)處理}for (int k=0;k<100;++k)for (int i=0;i<100;++i)for (int j=0;j<100;++j)if (c[i][k]+c[k][j]<c[i][j])//求最短路{c[i][j]=c[i][k]+c[k][j];a[i][j]=a[i][k]+a[k][j];}else if (c[i][k]+c[k][j]==c[i][j]&&a[i][k]+a[k][j]<a[i][j]) a[i][j]=a[i][k]+a[k][j];//求最小代價(jià)printf("%d",a[0][1]); }

總結(jié)

以上是生活随笔為你收集整理的【Floyed】廉价最短路径的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。