现在的位置: 首页 > 算法 > 正文

zoj1655

2019年03月01日 算法 ⁄ 共 970字 ⁄ 字号 评论关闭

秒速赛车公式 www.l19l7.cn

//反过来找比较简单

#include <cstdio>

#include <iostream>
#include <string.h>
using namespace std;
double map[110][110];
double weight[110];
double dist[110];
void dijkstar(int sta,int n)
{
int i,j,mark;
double maxi;
bool flag[100];
memset(flag,0,sizeof(flag));
memset(dist,0,sizeof(dist));
flag[sta]=1;
dist[sta]=1;
for(i=1;i<=n;i++)
{
maxi=-1;
for(j=1;j<=n;j++)
{
if(!flag[j])
{
if(map[sta][j]!=-1&&dist[j]<dist[sta]*map[sta][j])
dist[j]=dist[sta]*map[sta][j];
else if(map[sta][j]!=-1&&dist[j]==0)
dist[j]=dist[sta]*map[sta][j];
if(maxi<dist[j]&&dist[j]!=0)
{
mark=j;
maxi=dist[j];
}
}
}
if(maxi==-1)
break;
sta=mark;
flag[sta]=1;
}
}
void output( int n ) ?
{ ?
int i; ?
double sum; ?
sum=0.0; ?
for( i=1;i<n;i++ ) ?
{ ?
sum+=dist[i]*weight[i]; ?
} ?
printf( "%.2f\n",sum ); ?
} ?
int main ()
{
int n,m,a,b,i,j;
double rate;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
map[i][j]=-1;
for(i=1;i<n;i++)
scanf("%lf",&weight[i]);
for(i=1;i<=m;i++)
{
scanf("%d%d%lf",&a,&b,&rate);
if(1-rate>map[a][b])
map[a][b]=map[b][a]=1-rate;
}
dijkstar(n,n);
output(n);
}
return 0;
}

抱歉!评论已关闭.

  • 新疆各族群众体验端午传统文化 2019-05-25
  • 【十九大·理论新视野】动漫:“社会主义现代化强国”如何建成 2019-05-25
  • 太原黑臭水体治理接受国家专项督查 2019-05-24
  • 白芦笋:一年一会矜贵食 2019-05-24
  • 安徽通报2018年上半年全省旅游投诉情况 2019-05-24
  • 女性之声——全国妇联 2019-05-23
  • 【新华微视评】偏远农村的“智慧消防” 2019-05-23
  • 万花瞳:万花迷人眼 慧瞳观天下 2019-05-23
  • 视频:热心球迷!陈奕迅吴秀波惊现世界杯开幕式现场 2019-05-22
  • 【北京神龙京津车型报价】北京神龙京津4S店车型价格 2019-05-22
  • 国外看中国科技:中国隧道技术发展迅速享誉世界 2019-05-22
  • 孕妇在巴黎大区快线列车上产子 宝宝获赠“大礼” 2019-05-22
  • 【学习时刻】中国人民大学副校长刘元春:中央经济工作会议的四大亮点 2019-05-21
  • 环球佳酿举行新品发布会 百余款酒品集中发售 2019-05-21
  • 改造后的老旧楼房抗震能力是否提高?新老建筑是否共用逃生通道? 2019-05-21
  • 892| 504| 621| 892| 339| 457| 947| 844| 41| 396|