hdu4318 最短路变形
2024-09-06 17:29:34
和hdu有一题差不多。给的是损失比,1-c%就是保存了多少,找出最大的保存率即可。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
#define inf 99999999
#define maxn 50010
#define maxm maxn*51
int n,e,head[maxn],pre[maxm],nex[maxm];
double cost[maxm],dis[maxn];
bool vis[maxn];
queue<int> q;
void add(int u,int v,double c)
{
pre[e]=v;
nex[e]=head[u];
cost[e]=c;
head[u]=e++;
}
double spfa(int st,int end)
{
memset(dis,,sizeof(dis));
dis[st]=;
q.push(st);
while(!q.empty())
{
int u=q.front();
vis[u]=;
q.pop();
for(int i=head[u];i!=-;i=nex[i])
if(dis[pre[i]]<dis[u]*(-cost[i]))
{
dis[pre[i]]=dis[u]*(-cost[i]);
if(!vis[pre[i]])
{
q.push(pre[i]);
vis[pre[i]]=;
}
}
}
return dis[end];
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
e=;
memset(head,-,sizeof(head));
for(int i=;i<=n;i++)
{
int m;
scanf("%d",&m);
for(int j=;j<m;j++)
{
int u,c;
scanf("%d%d",&u,&c);
add(i,u,c*1.0/);
}
}
int st,end,tot;
scanf("%d%d%d",&st,&end,&tot);
double px=spfa(st,end);
if(px==)
printf("IMPOSSIBLE!\n");
else
printf("%.2f\n",(-px)*tot); }
return ;
}
最新文章
- 初识Windows窗体(包括各种控件,属性,方法)
- iOS开发之网络编程--1、NSURLSession的基本使用
- java读取word内容
- ganymedssh2 java执行linux命令
- vim配置python开发环境
- Python3 IO
- php 删除文件夹及文件
- Ubuntu16.04LTS安装
- Shell中的正则表达式及字符串处理
- 技巧收集-W1701
- raid制作(转载)
- vs调试正确显示utf8格式字符串
- 使用ADO.NET查询和操作数据库
- 使用 GDB 调试需要命令行参数的程序
- Android APP性能测试笔记(一)
- easyui中combobox 取值
- Java笔记Spring(三)
- MYSQL中常用的强制性操作(例如强制索引)
- 【本地服务器】利用openssl生成证书
- SQL语句之 多表管理