[POI2007]旅游景点atr

2023-12-24 10:40
文章标签 poi2007 旅游景点 atr

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

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,总长度为19。注意FGD为了从城市2到城市4可以路过城市3,但不在城市3停留。这样就不违反FGD的要求了。并且由于FGD想要走最短的路径,因此这个方案正是FGD需要的。

Input
第一行包含3个整数N(2<=N<=20000),M(1<=M<=200000),K(0<=K<=20),意义如上所述。
之后有q条限制,每次给一对\(x_i,y_i\),代表\(x_i\)要在\(y_i\)之前休息过

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
1214431-20180418152931540-1790526644.jpg
上图为题中所给出的例子


这题我不想说什么,题目输入描述都不讲清楚……看到k<=20,这不直接上状压吗
把1~k+1这些点之间的距离去全部处理出来,然后对于每个点记上一个限制,就可以愉快地用状压DP了
有K=0的情况,被坑了

/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){int x=0,f=1;char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar())  if (ch=='-')    f=-1;for (;ch>='0'&&ch<='9';ch=getchar())    x=(x<<3)+(x<<1)+ch-'0';return x*f;
}
inline void write(int x){if (x>=10)  write(x/10);putchar(x%10+'0');
}
const int N=2e4,M=2e5,K=20;
int pre[(M<<1)+10],now[N+10],child[(M<<1)+10],val[(M<<1)+10];
int h[N+10],deep[N+10];
bool vis[N+10];
int dis[K+5][K+5],f[21][1<<K],v[K+5];
int n,m,k,tot,Ans=inf;
void join(int x,int y,int z){pre[++tot]=now[x],now[x]=tot,child[tot]=y,val[tot]=z;}
void SPFA(int x){//预处理,dijkstra会快一些,但是我懒memset(vis,0,sizeof(vis));memset(deep,63,sizeof(deep));int head=0,tail=1;h[1]=x,vis[x]=1,deep[x]=0;while (head!=tail){if (++head>N)   head=1;int Now=h[head];for (int p=now[Now],son=child[p];p;p=pre[p],son=child[p]){if (deep[son]>deep[Now]+val[p]){deep[son]=deep[Now]+val[p];if (!vis[son]){if (++tail>N)   tail=1;vis[h[tail]=son]=1;}}}vis[Now]=0;}for (int i=1;i<=k+1;i++)    dis[x][i]=deep[i];dis[x][0]=deep[n];
}
void dp(){memset(f,63,sizeof(f));for (int i=1;i<=k;i++)  if (!v[i])  f[i][1<<(i-1)]=dis[1][i+1];for (int sta=1;sta<1<<k;sta++){for (int i=1;i<=k;i++){if ((f[i][sta]==inf)||(!(sta&(1<<(i-1)))))  continue;for (int j=1;j<=k;j++){if (((v[j]&sta)==v[j])&&(!(sta&(1<<(j-1))))){f[j][sta|(1<<(j-1))]=min(f[j][sta|(1<<(j-1))],f[i][sta]+dis[i+1][j+1]);}}}}
}
int main(){n=read(),m=read(),k=read();for (int i=1;i<=m;i++){int x=read(),y=read(),z=read();join(x,y,z),join(y,x,z);}if (!k){SPFA(1);printf("%d\n",deep[n]);return 0;}//特判for (int i=1;i<=k+1;i++)    SPFA(i);int q=read();for (int i=1;i<=q;i++){//由于他要经过的点是2~k+1,所以处理起来会有点小恶心int x=read(),y=read();v[y-1]|=1<<(x-2);}dp();for (int i=1;i<=k;i++)  Ans=min(Ans,f[i][(1<<k)-1]+dis[i+1][0]);printf("%d\n",Ans);
}

转载于:https://www.cnblogs.com/Wolfycz/p/8875264.html

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



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

相关文章

[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可能无法准确反映实际波动可适用