22.网络提速（最短路）
時(shí)間限制: 1 s
?空間限制: 128000 KB
?題目等級(jí) : 黃金 Gold
題解
?查看運(yùn)行結(jié)果
題目描述?Description
某學(xué)校的校園網(wǎng)由n(1<=n<=50)臺(tái)計(jì)算機(jī)組成，計(jì)算機(jī)之間由網(wǎng)線相連，如圖5。其中頂點(diǎn)代表計(jì)算機(jī)，邊代表網(wǎng)線。正如你所見(jiàn)，不同網(wǎng)線的傳輸能力不盡相同，例如計(jì)算機(jī)1與計(jì)算機(jī)2之間傳輸信息需要34秒，而計(jì)算機(jī)2與計(jì)算機(jī)3之間的傳輸信息只要10秒。計(jì)算機(jī)1與計(jì)算機(jī)5之間傳輸信息需要44秒，途徑為機(jī)1到機(jī)3到機(jī)5。
現(xiàn)學(xué)校購(gòu)買(mǎi)了m(1<=m<=10)臺(tái)加速設(shè)備，每臺(tái)設(shè)備可作用于一條網(wǎng)線，使網(wǎng)線上傳輸信息用時(shí)減半。多臺(tái)設(shè)備可用于同一條網(wǎng)線，其效果疊加，即用兩臺(tái)設(shè)備，用時(shí)為原來(lái)的1/4，用三臺(tái)設(shè)備，用時(shí)為原來(lái)的1/8。如何合理使用這些設(shè)備，使計(jì)算機(jī)1到計(jì)算機(jī)n傳輸用時(shí)最少，這個(gè)問(wèn)題急需解決。校方請(qǐng)你編程解決這個(gè)問(wèn)題。例如圖5，若m=2，則將兩臺(tái)設(shè)備分別用于1-3，3-5的線路，傳輸用時(shí)可減少為22秒，這是最佳解。
輸入描述?Input Description
第一行先輸入n,m。以下n行，每行有n個(gè)實(shí)數(shù)。第i行第j列的數(shù)為計(jì)算機(jī)i與計(jì)算機(jī)j之間網(wǎng)線的傳輸用時(shí)，0表示它們之間沒(méi)有網(wǎng)線連接。注意輸入數(shù)據(jù)中，從計(jì)算機(jī)1到計(jì)算機(jī)n至少有一條網(wǎng)路。
?
輸出描述?Output Description
輸出計(jì)算機(jī)1與計(jì)算機(jī)n之間傳輸信息的最短時(shí)間。(保留兩位小數(shù))
樣例輸入?Sample Input
5?2
0?34?24?0?0
34?0?10?12?0
24?10?0?16?20
0?12?16?0?30
0?0?20?30?0
樣例輸出?Sample Output
22.00
數(shù)據(jù)范圍及提示?Data Size & Hint
分類(lèi)標(biāo)簽?Tags?點(diǎn)此展開(kāi)?
思路：先找出1—n的最短路，再?gòu)淖疃搪飞?#xff0c;從邊的權(quán)值的大到小順序除二知道m(xù)==0為止
?
代碼：
#include
using namespace std;
const int maxn=51;
#include
#include
#include
int n,m,p[maxn][maxn],dist[maxn],pre[maxn],visit[maxn]={0},t=0;
double sum=0;
struct Edge{
?????? int from,to;
?????? double weigh;//因?yàn)樽詈蠼Y(jié)果保存2位小數(shù)，所以權(quán)值也要是浮點(diǎn)數(shù)才行
};
Edge edge[maxn*maxn];//存最短路徑的邊
void input();
void dijkstra();
int cmp(const Edge &a,const Edge &b)
{
?????? return a.weigh>b.weigh;
}
void stim()
{
?????? while(pre[n]!=0)//把最短路徑放到結(jié)構(gòu)體中
?????? {
????????????? edge[++t].from=pre[n];
????????????? edge[t].to=n;
????????????? edge[t].weigh=p[pre[n]][n];
????????????? n=pre[n];
????????????????????
?????? }
?????? sort(edge+1,edge+t+1,cmp);//巴結(jié)構(gòu)體的邊權(quán)有大到小排序
?????? int edgel;
? while(m)
? {
???? edgel=1;//比較指針
?????? ?while(m)
?????? ?{
????????????? while(edge[edgel].weigh>edge[edgel+1].weigh)//把大數(shù)一次性除得比第二個(gè)數(shù)小
????????????? {
???????????????????? m--;
???????????????????? edge[edgel].weigh/=2;
???????????????????? if(m==0)return;
????????????????????
????????????? }
????????????? edgel++;//比較2與3
????????????? if(edgel==t) //比到最后一個(gè)時(shí)，再重新排序，由大到小，分別/2
???????????????????? break;
?????????????
?????????????
?????? ?}
?????? sort(edge+1,edge+t+1,cmp);
? }
?
}
int main()
{
?????? input();
?????? dijkstra();
?????? stim();
?????? for(int i=1;i<=t;++i)
?????? sum+=edge[i].weigh;
?????? printf("%.2lf",sum);
?????? return 0;
}
void dijkstra()
{
??? visit[1]=1;
?????? pre[1]=0;//把1的前驅(qū)設(shè)為0
?????? dist[1]=0;//注意
?????? for(int i=2;i<=n;++i)
??? ?????? if(dist[i]<99999)
????????????? ?pre[i]=1;?????? //把前驅(qū)是1的先設(shè)上，因?yàn)橄旅嫠惴?#xff0c;不會(huì)給他設(shè)
?????? for(int i=1;i<=n;++i)
?????? {
????????????? int min=99999,k=0;
????????????? for(int j=1;j<=n;++j)
????????????? {
???????????????????? if(dist[j]
????????????? ??? {
????????????? ??? ?????? k=j;
????????????? ??? ?????? min=dist[j];
???????????????????? }
????????????? }
????????????? if(k==0) break;
????????????? visit[k]=1;
????????????? for(int j=1;j<=n;++j)
????????????? {
???????????????????? if(dist[j]>dist[k]+p[k][j])
???????????????????? {
??????????????????????????? dist[j]=dist[k]+p[k][j];
??????????????????????????? pre[j]=k;//記錄前驅(qū)
???????????????????? }
????????????? }
?????? }
??????
}
void input()
{
?????? scanf("%d%d",&n,&m);
?????? for(int i=1;i<=n;++i)
?????? ? for(int j=1;j<=n;++j)
?????? ? {
?????? ? ??? scanf("%d",&p[i][j]);
?????? ? ??? if(p[i][j]==0)
?????? ? ??? p[i][j]=99999;
?????? ? ??? if(i==1)
?????? ? ??? dist[j]=p[i][j];
?????? ? }
}
轉(zhuǎn)載于:https://www.cnblogs.com/csgc0131123/p/5290510.html
總結(jié)
以上是生活随笔為你收集整理的22.网络提速（最短路）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 在Eclipse中打开Hadoop工程
- 下一篇： 【UNIX网络编程（二）】基本TCP套接