P3451 [POI2007]ATR-Tourist Attractions

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


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

    最新讨论 显示

    推荐的相关题目 显示





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


    接下来一行一个整数$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
    2 3
    3 4
    3 5
    输出样例#1: 复制