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

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-03-19
  • 回复@真理论者:你天天在强坛攻击爱因斯坦是不是劳动?创造价值么?负价值也! 2019-03-19
  • 北京天安门广场更换花卉 2019-03-18
  • 党的自我革命是伟大社会革命的强大动力(深入学习贯彻习近平新时代中国特色社会主义思想) 2019-03-18
  • 人民日报人民时评:让安全生产理念成为基本共识 2019-03-18
  • “人民体育 健康中国”马拉松系列赛北京站 2019-03-17
  • 识破“假大学”并没那么难 2019-03-17
  • 佛山:用公积金买装配式住房 贷款额度或可上浮20% ——凤凰网房产北京 2019-03-17
  • 奥运冠军寄语Running Together国际迷你马拉松—在线播放—《奥运冠军寄语Running Together国际迷你马拉松》—体育—优酷网,视频高清在线观看 2019-03-17
  • 【理上网来喜迎十九大】西班牙学者:大国外交令中国成为建立世界新秩序的中流砥柱 2019-03-16
  • 马上背!十九大报告中的四个“新” 2019-03-16
  • 呼市赛罕区南门外小学开展庆父亲节亲子趣味足球赛 2019-03-16
  • 2017大皖客户端徽派栏目全面回顾宣传片 2019-03-15
  • 回复@海之宁:你想自主劳动?全民所有的生产资料凭啥让你自主? 2019-03-15
  • 重庆市南岸区:探索建立“微益坊” 2019-03-15
  • 592| 832| 449| 430| 786| 752| 176| 355| 461| 321|