8288分类目录 8288分类目录 8288分类目录
  当前位置:海洋目录网 » 站长资讯 » 站长资讯 » 文章详细 订阅RssFeed

CF95C Volleyball

来源:本站原创 浏览:132次 时间:2021-10-11
题意翻译

给出一个图,双向边,边上有权值代表路的距离,然后每个点上有两个值,t,c,t代表能从这个点最远沿边走t,且不能在半路下来,花费是c 现在告诉你起点终点,问����,����最少的花费 点个数1000,边个数1000,边权1e9

By @partychicken

题目描述

Petya loves volleyball very much. One day he was running late for a volleyball match. Petya hasn't bought his own car yet, that's why he had to take a taxi. The city has n n n junctions, some of which are connected by two-way roads. The length of each road is defined by some positive integer number of meters; the roads can have different lengths.

Initially each junction has exactly one taxi standing there. The taxi driver from the i i i -th junction agrees to drive Petya (perhaps through several intermediate junctions) to some other junction if the travel distance is not more than ti t_{i} ti meters. Also, the cost of the ride doesn't depend on the distance and is equal to ci c_{i} ci bourles. Taxis can't stop in the middle of a road. Each taxi can be used no more than once. Petya can catch taxi only in the junction, where it stands initially.

At the moment Petya is located on the junction x x x and the volleyball stadium is on the junction y y y . Determine the minimum amount of money Petya will need to drive to the stadium.

输入输出格式

输入格式:

The first line contains two integers n n n and m m m ( 1<=n<=1000,0<=m<=1000) 1<=n<=1000,0<=m<=1000) 1<=n<=1000,0<=m<=1000) . They are the number of junctions and roads in the city correspondingly. The junctions are numbered from 1 1 1 to n n n , inclusive. The next line contains two integers x x x and y y y ( 1<=x,y<=n 1<=x,y<=n 1<=x,y<=n ). They are the numbers of the initial and final junctions correspondingly. Next m m m lines contain the roads' description. Each road is described by a group of three integers ui u_{i} ui , vi v_{i} vi , wi w_{i} wi ( 1<=ui,vi<=n,1<=wi<=109 1<=u_{i},v_{i}<=n,1<=w_{i}<=10^{9} 1<=ui,vi<=n,1<=wi<=109 ) — they are the numbers of the junctions connected by the road and the length of the road, correspondingly. The next n n n lines contain n n n pairs of integers ti t_{i} ti and ci c_{i} ci ( 1<=ti,ci<=109 1<=t_{i},c_{i}<=10^{9} 1<=ti,ci<=109 ), which describe the taxi driver that waits at the i i i -th junction — the maximum distance he can drive and the drive's cost. The road can't connect the junction with itself, but between a pair of junctions there can be more than one road. All consecutive numbers in each line are separated by exactly one space character.

输出格式:

If taxis can't drive Petya to the destination point, print "-1" (without the quotes). Otherwise, print the drive's minimum cost.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.

输入输出样例

输入样例#1: 

4 41 31 2 31 4 12 4 12 3 52 77 21 27 7

输出样例#1: 

9
说明

An optimal way — ride from the junction 1 to 2 (via junction 4), then from 2 to 3. It costs 7+2=9 bourles.

 

Solution:

  本题水。

  点数很小,先从每个点暴力最短路处理出该点的t范围内能到的点,并且建一张新图,然后只要在新图上再跑一遍最短路就好了。

代码:

/*Code by 520 -- 8.21*/#include#define il inline#define ll long long#define RE register#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)using namespace std;const int N=2000005;int n,m,s,t,a[N],b[N];int to[N],net[N],w[N],h[N],cnt;int To[N],Net[N],W[N],H[N],Cnt;ll dis[N];bool vis[N];struct node{    int u;    ll d;    bool operator<(const node &a)const{return d>a.d;}};int gi(){    int a=0;char x=getchar();    while(x<'0'||x>'9')x=getchar();    while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+(x^48),x=getchar();    return a;}il void add(int u,int v,int c){to[++cnt]=v,net[cnt]=h[u],w[cnt]=c,h[u]=cnt;}il void Add(int u,int v,int c){To[++cnt]=v,Net[cnt]=H[u],W[cnt]=c,H[u]=cnt;}queue<int>q;il void spfa(int x){    For(i,1,n) dis[i]=233333333333333;    q.push(x),dis[x]=0;    while(!q.empty()){        int u=q.front();q.pop();vis[u]=0;        for(RE int i=h[u];i;i=net[i])            if(dis[to[i]]>dis[u]+w[i]){                dis[to[i]]=dis[u]+w[i];                if(!vis[to[i]])q.push(to[i]),vis[to[i]]=1;            }    }    For(i,1,n) if(i!=x&&dis[i]<=a[x]) Add(x,i,b[x]);}priority_queueQ;il void dij(){    For(i,1,n) dis[i]=233333333333333;    dis[s]=0,Q.push(node({s,0}));    while(!Q.empty()){        node x=Q.top();Q.pop();        if(!vis[x.u]){            vis[x.u]=1;            for(RE int i=H[x.u];i;i=Net[i])                if(dis[To[i]]>dis[x.u]+W[i]){                    dis[To[i]]=dis[x.u]+W[i];                    if(!vis[To[i]]) Q.push(node({To[i],dis[To[i]]}));                }        }    }}il void init(){    n=gi(),m=gi(),s=gi(),t=gi();    int u,v,c;    For(i,1,m) u=gi(),v=gi(),c=gi(),add(u,v,c),add(v,u,c);    For(i,1,n) a[i]=gi(),b[i]=gi();    cnt=0;    For(i,1,n) spfa(i);    dij();    cout<<(dis[t]==233333333333333?-1:dis[t]);}int main(){    init();    return 0;}

 

  推荐站点

  • At-lib分类目录At-lib分类目录

    At-lib网站分类目录汇集全国所有高质量网站,是中国权威的中文网站分类目录,给站长提供免费网址目录提交收录和推荐最新最全的优秀网站大全是名站导航之家

    www.at-lib.cn
  • 中国链接目录中国链接目录

    中国链接目录简称链接目录,是收录优秀网站和淘宝网店的网站分类目录,为您提供优质的网址导航服务,也是网店进行收录推广,站长免费推广网站、加快百度收录、增加友情链接和网站外链的平台。

    www.cnlink.org
  • 35目录网35目录网

    35目录免费收录各类优秀网站,全力打造互动式网站目录,提供网站分类目录检索,关键字搜索功能。欢迎您向35目录推荐、提交优秀网站。

    www.35mulu.com
  • 就要爱网站目录就要爱网站目录

    就要爱网站目录,按主题和类别列出网站。所有提交的网站都经过人工审查,确保质量和无垃圾邮件的结果。

    www.912219.com
  • 伍佰目录伍佰目录

    伍佰网站目录免费收录各类优秀网站,全力打造互动式网站目录,提供网站分类目录检索,关键字搜索功能。欢迎您向伍佰目录推荐、提交优秀网站。

    www.wbwb.net