【BZOJ1097/POI2007】旅游景点atr

2023-12-24 10:40

本文主要是介绍【BZOJ1097/POI2007】旅游景点atr,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

                                   1097: [POI2007]旅游景点atr

                                                     Time Limit: 30 Sec  Memory Limit: 357 MB
                                                                 Submit: 2884  Solved: 804

Description

  FGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景,品尝风味小吃或者做其他的有趣
的事情。经过这些城市的顺序不是完全随意的,比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山,
而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的,他可以在某些旅行方案之间进行选择。由于
FGD非常讨厌乘车的颠簸,他希望在满足他的要求的情况下,旅行的距离尽量短,这样他就有足够的精力来欣赏风
景或者是泡MM了^_^.整个城市交通网络包含N个城市以及城市与城市之间的双向道路M条。城市自1至N依次编号,道
路亦然。没有从某个城市直接到它自己的道路,两个城市之间最多只有一条道路直接相连,但可以有多条连接两个
城市的路径。任意两条道路如果相遇,则相遇点也必然是这N个城市之一,在中途,由于修建了立交桥和下穿隧道
,道路是不会相交的。每条道路都有一个固定长度。在中途,FGD想要经过K(K<=N-2)个城市。成都编号为1,上海
编号为N,而FGD想要经过的N个城市编号依次为2,3,…,K+1.举例来说,假设交通网络如下图。FGD想要经过城市2,3,
4,5,并且在2停留的时候在3之前,而在4,5停留的时候在3之后。那么最短的旅行方案是1-2-4-3-4-5-8,总长度为1
9。注意FGD为了从城市2到城市4可以路过城市3,但不在城市3停留。这样就不违反FGD的要求了。并且由于FGD想要
走最短的路径,因此这个方案正是FGD需要的。

Input

  第一行包含3个整数N(2<=N<=20000),M(1<=M<=200000),K(0<=K<=20),意义如上所述。

Output

  只包含一行,包含一个整数,表示最短的旅行距离。

Sample Input

8 15 4
1 2 3
1 3 4
1 4 4
1 6 2
1 7 3
2 3 6
2 4 2
2 5 2
3 4 3
3 6 3
3 8 6
4 5 2
4 8 6
5 7 4
5 8 6
3
2 3
3 4
3 5

Sample Output

19

HINT

上面对应于题目中给出的例子。

 

解析:

       原题卡空间是真的恶心。。。

       所以正解是最短路dijkstra+状压DP。

       具体来说就是先算出两两停留位置之间的最短路,然后状压f[i][j]表示到停留过的状态为j现在停留在i的最短路。

 

代码:
 

#include <bits/stdc++.h>
using namespace std;const int Maxn=20005;
const int Maxm=200005;
int n,m,k,q,size,ans=1e9;
int pre[22],f[22][1<<21],bin[22];
int first[Maxn],d[22][22],dis[Maxn],vis[Maxn];
struct shu{int to,next,len;}edge[Maxm<<1];inline int get_int()
{int x=0,f=1;char c;for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());if(c=='-') f=-1,c=getchar();for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';return x*f;
}inline void build(int x,int y,int z){edge[++size].next=first[x],first[x]=size,edge[size].to=y,edge[size].len=z;}
inline void dijkstra(int s)
{priority_queue<pair<int,int> >q;for(int i=1;i<=n;i++) dis[i]=1e9;dis[s]=0;for(int i=1;i<=n;i++) vis[i]=0;q.push(make_pair(0,s));while(q.size()){int p=q.top().second;q.pop();if(vis[p]) continue;vis[p]=1;for(int u=first[p];u;u=edge[u].next){int to=edge[u].to;if(dis[to]>dis[p]+edge[u].len){dis[to]=dis[p]+edge[u].len;q.push(make_pair(-dis[to],to));}}}for(int i=1;i<=k+1;i++) d[s][i]=dis[i];d[s][0]=dis[n];
}
inline void init()
{bin[0]=1;for(int i=1;i<=21;i++) bin[i]=bin[i-1]<<1; n=get_int(),m=get_int(),k=get_int();for(int i=1;i<=m;i++){int x=get_int(),y=get_int(),z=get_int();build(x,y,z),build(y,x,z);}for(int i=1;i<=k+1;i++) dijkstra(i);q=get_int();while(q--){int x=get_int(),y=get_int();pre[y]|=bin[x-2];}
}
inline void solve()
{memset(f,0x3f,sizeof(f));f[1][0]=0;
//  for(int i=0;i<bin[k];i++)
//    for(int from=1;from<=k+1;from++)
//      if(f[from][i]<1e9)
//        for(int to=2;to<=k+1;to++)
//          if((pre[to]&i)==pre[to])
//            f[to][i|bin[to-2]]=min(f[to][i|bin[to-2]],f[from][i]+d[from][to]);for(int now=0;now<bin[k];now++)for(int x=1;x<=k+1;x++)if(f[x][now]<1e9)for(int i=2;i<=k+1;i++){int to=(now|bin[i-2]);if((now&pre[i])==pre[i])if(f[i][to]>f[x][now]+d[x][i])f[i][to]=f[x][now]+d[x][i];}for(int i=1;i<=k+1;i++) ans=min(ans,f[i][bin[k]-1]+d[i][0]);cout<<ans;
}
int main()
{init();solve();return 0;
}


 

这篇关于【BZOJ1097/POI2007】旅游景点atr的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/531508

相关文章

[1678]旅游景点信息Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点      JSP 旅游景点信息管理系统是一套完善的java web信息管理系统,对理解JSP java编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要采用B/S模式开发。开发环境为TOMCAT7.0,Myeclipse8.5开发,数据库为Mysql5.0,使用java语言开发。 java web旅游景点管理系统 二、功能介绍 前台 首页 景点浏览,景点评论 门

ISO7816中的ATR简介

智能卡(此处主要指接触式CPU卡)本身始终处于被动的状态,所以终端设备在和智能卡进行数据交互的时候,需要首先给智能卡发指令,智能卡才会对应地给出应答。而智能卡告诉终端的第一句话就是ATR,亦即“复位应答”。 想象一下,如果让你为智能卡设计一个通讯协议,该怎么设计? 因为ATR是智能卡上电后说的第一句话,所以一定要确保这句话被准确地接收。在设计通讯协议的时候有必要设计一个可以让收发双方进行“握手

ATR介绍

7816协议上摘抄的一段 ATR:复位应答,它是一系列字节的值,这些字节是由卡作为对复位命令的响应发送给接口设备的 ATR的字符序列,首先一个初始字符TS,TS后面按照下面的次序最多32个字符: T0 TA(i) TB(i) TC() TD() ... T1 T2 Tk ... Tck T0

全国航空机场分布矢量数据/旅游景点poi/全国港口码头分布/地铁站分布/火车站分布/POI矢量数据

民用航空机场是指针对包括跑道型机场、表面直升机场、高架直升机场、船上直升机场、直升机水上平台、滑翔机场、水上机场、有人操纵气球施放场以及其他专供民用航空器起降的划定区域。民用航空机场分为通用航空机场和公共运输机场;不包括临时机场和专用机场。         根据中国民航局发布的《通用机场分类管理办法》、《通用航空经营许可管理规定》等,收集全国民用航空机场的位置及属性信息,并将其进行空间化处理,

基于spark的热门旅游景点门票数据可视化分析系统

热门旅游景点数据分析系统综合网络空间开发设计要求。目的是将传统管理方式转换为在网上管理,完成热门旅游景点数据分析管理的方便快捷、安全性高、交易规范做了保障,目标明确。热门旅游景点数据分析系统功能主要包括个人中心、门票信息管理、名宿信息管理、系统管理等进行管理。整个的系统的开发运用Python技术, django框架,以及MySql数据库技术的大力支持下同步完成该系统的开发,实现了热门旅游景点数据分

量化指标ATR(Average True Range真实波动幅度均值)及其发明人Welles Wilder的前世今生

关于证券市场中常用指标,网上资料看起来挺多,但是如果想要深入了解就发现各种都是一路抄,本ID对指标进行详细调研,研究几大指标的前世今生 Welles Wilder是谁? 真实波动幅度均值(ATR)是威尔斯·威尔德(J. Welles Wilder)出版于1978年的《New Concepts in Technical Trading Systems》一书种公布的波动率指标。 J.

Android Studio实现内容丰富的安卓旅游景点预定

获取源码请点击文章末尾QQ名片联系,源码不免费,尊重创作,尊重劳动 1.开发环境 android stuido3.6 jak1.8 eclipse mysql tomcat  2.功能介绍 安卓端: 1.注册登录 2.查看景点列表 3.查看景点详情 4.景点预定 5.购物车支付结算功能 6.我的订单 7.景点评论功能 服务端: 1.管理员登录功能 2.用户管理 3

java SSM旅游景点与公交线路查询系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计

一、源码特点     java SSM旅游景点与公交线路查询系统是一套完善的web设计系统(系统采用SSM框架进行设计开发,spring+springMVC+mybatis),对理解JSP java编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要采用B/S模式开发。开发环境为TOMCAT7.0,Myeclipse8.5开发,数据库为Mysql5.0,使用java语言开发。 ssm

Vue.js+SpringBoot开发海南旅游景点推荐系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 用户端2.2 管理员端 三、系统展示四、核心代码4.1 随机景点推荐4.2 景点评价4.3 协同推荐算法4.4 网站登录4.5 查询景点美食 五、免责说明 一、摘要 1.1 项目介绍 基于Vue+SpringBoot+MySQL的海南旅游推荐系统,基于协同推荐算法,包括用户网页和管理后台,包含景点类

Python 实现 ATR 指标计算(真实波幅):股票技术分析的利器系列(10)

Python 实现 ATR 指标计算(真实波幅):股票技术分析的利器系列(10) 介绍算法解释 代码rolling函数介绍核心代码 完整代码 介绍 ATR(真实波幅)是一种技术指标,用于衡量市场波动性的程度 优点缺点提供波动性度量,有助于风险管理和交易决策ATR本身不提供买卖信号,需要结合其他指标使用简单易懂,计算方法清晰对于极端行情,ATR可能无法准确反映实际波动可适用