P3451 [POI2007]ATR-Tourist Attractions

    • 62通过
    • 978提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 最短路 状态压缩,状压 POI 2007 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms-3000ms / 64MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    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需要的。

    第一行三个整数$n,m,k$ ;

    接下来的$m$行描述路径,每行$3$个整数,第$i+1$行的$p_i,q_i,l_i$表示$p_i$和$q_i$之间有一条长为$l_i$的路。

    接下来一行一个整数$g$,$0 \le g \le k(k+1)/2$,表示有$g$个要求。

    【数据范围】

    $2 <= n <= 20000$,$1 <= m <= 200000$,$0 <= k <= 20$且$k <= n-2$
    $1 <= pi <= qi <= n$,$1 <= li <= 1000$

    题目描述

    Byteasar travels from Bitingham to Byteburg. He wants to visit some must-see sites along the way, includingsome interesting monuments, fine restaurants, and numerous other tourist attractions. The order, which hevisits the places in, is not entirely unimportant. For example, Byteasar would rather not climb the peakytower of the Bitfork Castle right after a lavish dinner in Digitest, and, likewise, he would drop in to Zip City(called by some Sip City) for a cup of the famous Compresso coffee after dinner, rather than before.

    Luckily,his tour is, to some extent, flexible and he can choose between some orders. As a result of horrendous petrolprices, he'd like to follow the shortest possible route, for economy's sake. Be a good friend and help himdetermine the length of the shortest path that meets his requirements.

    The system of roads consists of $n$ sites and $m$ roads connecting them. The sites are numbered from $1$ to $n$,and so are the roads (from $1$ to $m$). Each road links a pair of different sites and is bidirectional. Different roadsmeet only at sites (which are their endpoints) and do not cross outside the sites, thanks to a clever system offlyovers and tunnels. Each road has a certain length. A pair of sites can be connected directly by at most oneroad, though there can be many paths consisting of at least two direct roads between them.

    Let $k$ denote the number of sites Byteasar wants to visit. Bitingham has number $1$ in the numbering, Byteburg has number $n$, and the sites Byteasar wants to visit have numbers $2,3,\cdots,k+1$.

    An exemplary system of roads is shown in the figure. Suppose Byteasar wants to visit the sites 2, 3, 4 and5, and he would like to visit 2 before 3, and 4 and 5 after 3. Then the shortest route leads through sites 1, 2,4, 3, 4, 5, 8 and its length is 19.

    Note that the site 4 appears on the route both before and after the site 3. It is perfectly OK and means thatByteasar will not stop there before visiting site 3, since his requirements disallow it. He is, however, allowedto pass through the site 4 without stopping before visiting the site 3 - and this is exactly what he is going todo!

    TaskWrite a programme that:

    reads from the standard input the description of the system of roads, the list of sites which Byteasar has chosen to visit and the restrictions regarding the order in which he wants to visit them, determines length of the shortest route leading in an appropriate order through all the chosen sites, writes the result to the standard output.

    输入输出格式

    输入格式:

    In the first line of the standard input there are three integers $n$, $m$ and $k$, separated by single spaces,$2\le n\le 20\ 000$, $1\le m\le 200\ 000$, $0\le k\le 20$; furthermore, inequality $k\le n-2$ holds.

    The following $m$ lines contain the descriptions of the roads, exactly one in each line. The $(i+1)$'th linecontains three integers $p_i$, $q_i$ and $l_i$, separated by single spaces,$1\le p_i<q_i\le n$, $1\le l_i\le 1\ 000$.These numbersdenote a road linking the sites $p_i$ and $q_i$ of length $l_i$. You can safely assume that for each set of test data it ispossible to get from Bitingham to Byteburg and each of the sites Byteasar wants to visit.

    In the $(m+1)$'th line there is one integer $g$, $0\le g\le \frac{k\cdot (k-1)}{2}$.

    It is the number of restrictions regarding theorder in which Byteasar wants to visit the sites of his selection. These restrictions are given in the following $g$ lines, one in each line. The $(m+i+1)$'th line contains two integers $r_i$ and $s_i$ separated by a single space,$2\le r_i\le k+1$, $2\le s_i\le k+1$, $r_i\ne s_i$.

    The pair $r_i$ and $s_i$ means that Byteasar wants to visit the site $r_i$ beforevisiting the site $s_i$. It does not, however, prevent him from passing through $s_i$ before visiting $r_i$ nor passingthrough $r_i$ after having visited $s_i$. He is free to do so, as long as he does not stop by and visit the touristattractions. It is guaranteed that for each set of test data at least one order of visiting the selected sites whilesatisfying all the restrictions exists. 接下来g行,每行两个整数ri,si(2<=ri<=k+1,2<=si<=k+1),表示在si停留之前要先在ri停留(停留不等于经过)。

    输出格式:

    In the first and only line of the standard output one integer should be written, i.e. the length of the shortestpath from Bitingham to Byteburg passing in a proper order through all the sites Byteasar has selected.

    输入输出样例

    输入样例#1: 复制
    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
    输出样例#1: 复制
    19
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。