洛谷 U10223 Cx大帝远征埃及
2024-08-23 14:51:13
题目背景
众所周知,Cx是一个宇宙大犇。Cx能文善武,一直在为大一统的实现而努力奋斗着。Cx将调用他的精锐军队,一个精锐士兵最多可以战胜十个埃及士兵。同时Cx是个爱才的人,他想要制定一份能使在占领埃及的前提下,使自己的军队损失最小的作战方案。Cx可做好了充分的准备,他收集到了很多情报,经过了长期的准备,在今天这个伟大的日子,他终于作下了远征埃及的决定!
题目描述
Cx将会把他收集到的所有情报都汇总给你(当然不能有什么遗漏的),情报的内容包括了埃及的所有城市所驻扎的军队人数,和与其单向连通的城市(路程什么的对千里马来说不算什么)。编号1的城市即为首都,占领首都即战争胜利!他将会告诉你他调度的军队人数。
输入输出格式
输入格式:
第一行三个整数n和m,sum。n表示埃及的所有城市个数,m表示Cx大帝开始出征的城市标号,sum表示精锐军队的人数。
以下的n行,第i+1行即为关于埃及编号为i的城市的情报,第一个整数ai表示在此驻扎的军队人数,第二个整数pi表示与此城市连通的城市数目,接下来pi个整数为与其连通的城市编号。
输出格式:
第一行输出Cx大帝要想完成占领埃及的目标的最优攻占城市顺序方案。第二行输出精锐军队剩余的人数,详细格式见输出样例。如军队的人数过少无法使Cx大帝占领埃及,则输出"No way!”
输入输出样例
输入样例#1:
4 3 10
30 0
13 1 1
7 2 4 2
3 1 1
输出样例#1:
3->4->1
6
说明
样例说明:最少需要对付的埃及士兵为40个,而精锐士兵以一敌十,所以最后还有6个存活。 数据保证p1=0。
士兵杀8个死不了,下一次再解决两个就GG了。
对于100%的数据: 2<=n<=50000 pi<=100
WA了8遍的最小生成树
把堆优化dijkstra改为spfa才过
#include <ctype.h>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#define N 500005 using namespace std;
queue<int>q;
vector<int>vec;
void read(int &x)
{
x=;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*+ch-'',ch=getchar();
}
struct node
{
int next,to;
}edge[N<<];
bool vis[N];
int pre[N],n,cnt,dis[N],head[N],m,num,sum[N];
void add(int u,int v)
{
edge[++cnt].next=head[u];
edge[cnt].to=v;
head[u]=cnt;
}
void spfa(int x)
{
vis[x]=;
dis[x]=sum[x];
q.push(x);
while(!q.empty())
{
int tp=q.front();q.pop();
vis[tp]=;
for(int i=head[tp];i;i=edge[i].next)
{
if(dis[edge[i].to]>dis[tp]+sum[edge[i].to])
{
dis[edge[i].to]=dis[tp]+sum[edge[i].to];
pre[edge[i].to]=tp;
if(!vis[edge[i].to])
{
q.push(edge[i].to);
vis[edge[i].to]=;
}
}
}
}
}
int main()
{
read(n);
read(m);
read(num);
for(int b,i=;i<=n;i++)
{
read(sum[i]);
read(b);
for(int t,j=;j<=b;j++)
{
read(t);
add(i,t);
}
}
for(int i=;i<=n;i++) dis[i]=0x7ffffff;
spfa(m);
if(dis[]>num*)
{
printf("No way!");
return ;
}
int start=,end=m;
while(start!=end)
{
vec.push_back(start);
start=pre[start];
}
printf("%d",m);
for(int i=vec.size()-;i>=;i--) printf("->%d",vec[i]);
printf("\n%d",num-dis[]/);
return ;
}
最新文章
- 线程的2个ID
- asp.net正则表达式提取网页网址、标题、图片实例以及过滤所有HTML标签实例
- sdutoj 2623 The number of steps
- struts2总结四:Action与Form表单的交互
- 较复杂js的书写格式
- DIY Ruby CPU 分析——Part III
- Sencha touch Panel之间的跳转(如不使用TabPanel或者Carousel控件而产生跳转的动画效果)
- 微微信.NET:开源的ASP.NET微信公众号应用平台
- 解决Windows内存问题的两个小工具RamMap和VMMap(这个更牛更好)
- [编织消息框架][网络IO模型]aio
- 大数据处理架构hadoop
- gitlab操作指南
- java中的取整(/)和求余(%)
- 关闭mac的SIP + 一定有用的删除mac自带ABC的方法
- cordova原生页面切换效果插件的使用:com.telerik.plugins.nativepagetransitions
- day24 包
- 支持向量机(理论+opencv实现)
- 【CF662C】Binary Table
- Java HashMap的工作原理
- Navicat 12 连接 Mysql8.0 使用日志