P3547 [POI2013]CEN-Price List

    • 23通过
    • 87提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 广度优先搜索,BFS POI 2013 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Railway has always been the most popular mean of transport in Byteotia.

    Out of $n$ towns in the land, $m$ pairs are connected by track segments belonging to Byteotian State Railways (BSR).

    The tracks do not cross outside of towns, and may lead through picturesque bridges and somewhat less picturesque tunnels.

    The ticket for travelling between any two towns directly connected by rail costs $a$ bythalers.

    Currently the transportation market in Byteotia is changing.

    As of now, BSR faces a new competitor: Byteotian Airlines (BA).

    BA plans to operate flights between some pairs of towns.

    Since Byteotian railways are quite comfortable, the BA board has decided to operate flights only between pairs of towns that are not directly connected by rail. Due to economy, BA will fly only between towns for which the cheapest railway connection requires exactly one change.

    The ticket for each such flight is going to cost $b$ bythalers.

    To help Byteotian citizens in planning their trips, the Byteotian Ministry for Transport (BMT) has decided to issue leaflets specifying the cheapest routes between all possible towns. A sequence of an arbitrary number of direct railway or airplane connections is called a route. A BMT officer by the name of Byteasar has been commissioned with the task of preparing the price list for the leaflets.

    Could you help him in writing a program that will determine the right prices?

    Let us clarify that all the connections in Byteotia, both by railway and airplane, are bidirectional.

    给一个无向图,边权均为a,然后将原来图中满足最短路等于2a所有的点对(x,y)之间再加一条长度为b的无向边,问操作之后点K到所有点的最短路是多少

    输入输出格式

    输入格式:

    The first line of the standard input contains five integers,$n$,$m$,$k$,$a$ and $b$ ($2\le n\le 100\ 000$, $\le m\le 100\ 000$, $1\le k\le n$, $1\le a,b\le 1\ 000$), separated by single spaces.

    The numbers $n$ and $m$ denote the number of towns and the number of direct railway connections in Byteotia, respectively.

    For simplicity, we number the towns in Byteotia from $1$ to $n$. The other numbers denote:$k$ - the number of the source town for which the connection prices are to be determined;$a$ - the price of a direct railway connection;$b$ - the price of a direct airplane connection.

    Each of the following $m$ lines contains a pair of integers $u_i$ and $v_i$($1\le u_i,v_i\le n$,$u_i\ne v_i$ for $i=1,2,\cdots,m$), separated by a single space, specifying the number of towns directly connected by tracks.

    You may assume that all towns are reachable by railway from the town no. $k$.

    输出格式:

    Your program should print $n$ lines to the standard output.

    The line no. $i$ (for $i=1,2,\cdots,n$) should contain a single integer:

    the cost of the cheapest route from town no. $k$ to town no. $i$.

    Among those, the line no. $k$ should contain the number $0$.

    输入输出样例

    输入样例#1: 复制
    5 5 1 3 2
    1 2
    2 3
    3 4
    4 5
    3 1
    
    输出样例#1: 复制
    0
    3
    3
    2
    5
    

    说明

    给一个无向图,边权均为a,然后将原来图中满足最短路等于2a所有的点对(x,y)之间再加一条长度为b的无向边,问操作之后点K到所有点的最短路是多少

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。