VIJOS 1119 Car的旅行路线
发布日期:2022-02-05 18:27:31 浏览次数:8 分类:技术文章

本文共 2667 字,大约阅读时间需要 8 分钟。

描述

又到暑假了,住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场,分别位于一个矩形的四个顶点上,同一个城市中两个机场之间有一条笔直的高速铁路,第I个城市中高速铁路了的单位里程价格为Ti,任意两个不同城市的机场之间均有航线,所有航线单位里程的价格均为t。

那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题,于是她来向你请教。找出一条从城市A到B的旅游路线,出发和到达城市中的机场可以任意选取,要求总的花费最少。

img

格式

输入格式

第一行有四个正整数s,t,A,B。S(0<S<=100)表示城市的个数,t表示飞机单位里程的价格,A,B分别为城市A,B的序号,(1<=A,B<=S)。

接下来有S行,其中第I行均有7个正整数xi1,yi1,xi2,yi2,xi3,yi3,Ti,这当中的(xi1,yi1),(xi2,yi2),(xi3,yi3)分别是第I个城市中任意三个机场的坐标,T I为第I个城市高速铁路单位里程的价格。

输出格式

输出最小费用(结果保留两位小数)

样例

样例输入

3 10 1 31 1 1 3 3 1 302 5 7 4 5 2 18 6 8 8 11 6 3

样例输出

47.55

限制

每个测试点1s

来源

NOIP2001第四题




很明显这是一个最短路的题目 最短路不是重点 重点是处理边

因为边太多了。。。而且还要自己找坐标。。。

就当Dijk的模板题了 


值得一提的是  同一城市的机场也可以走。。。怪不得不过样例。。。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int inf=999999999;struct self{
         
int i;double d;
bool operator<(const self &a1) const
{
return a1.d==d?a1.i
}};priority_queue q;double d[511];struct side{int x,y;double w;}s[400021];int first[400021],nxt[400021];struct node{int x,y;}g[511];int w[511];int m,n,Start,End,Cost;int a,b,c;bool chuizhi(int a,int b,int c){
int ax=g[b].x-g[a].x,bx=g[c].x-g[a].x;
int ay=g[b].y-g[a].y,by=g[c].y-g[a].y;
if(ax*bx+ay*by==0)return true;
return false;}void findforth(int i){
int pos=i*4;
int a=pos-3,b=pos-2,c=pos-1;
if(chuizhi(a,b,c)){g[pos].x=g[b].x-g[a].x+g[c].x;g[pos].y=g[b].y-g[a].y+g[c].y;}
if(chuizhi(b,a,c)){g[pos].x=g[a].x-g[b].x+g[c].x;g[pos].y=g[a].y-g[b].y+g[c].y;}
if(chuizhi(c,a,b)){g[pos].x=g[a].x-g[c].x+g[b].x;g[pos].y=g[a].y-g[c].y+g[b].y;}}void makeside(int x,int y,double w){
n++;
s[n].x=x;
s[n].y=y;
s[n].w=w;
nxt[n]=first[x];
first[x]=n;}double dis(int a,int b,int c){return sqrt((g[a].x-g[b].x)*(g[a].x-g[b].x)+(g[a].y-g[b].y)*(g[a].y-g[b].y))*c;}void dijk(){
int a,b;
for(a=0;a<=m+4;a++)d[a]=inf;
d[0]=0;
q.push((self){0,0});
while(!q.empty())
{
self u=q.top();q.pop();
if(u.d!=d[u.i])continue;
for(int e=first[u.i];e!=-1;e=nxt[e])
if(d[s[e].y]>d[u.i]+s[e].w)
{
d[s[e].y]=d[u.i]+s[e].w;
q.push((self){s[e].y,d[s[e].y]});
}
}}int main(){
memset(first,-1,sizeof(first));
memset(nxt,-1,sizeof(nxt));
scanf("%d%d%d%d",&m,&Cost,&Start,&End);
for(a=1;a<=m;a++)
{
for(b=a*4-3;b<=a*4-1;b++)scanf("%d%d",&g[b].x,&g[b].y);
scanf("%d",&w[a]);
findforth(a);
for(b=a*4-3;b<=a*4;b++)
for(c=a*4-3;c<=a*4;c++)
if(b!=c)makeside(b,c,dis(b,c,w[a]));
}
m*=4;
for(a=1;a<=m;a++)
for(b=1;b<=m;b++)
//if(abs(a-b)>=4)
makeside(a,b,dis(a,b,Cost));
makeside(0,Start*4-3,0);
makeside(0,Start*4-2,0);
makeside(0,Start*4-1,0);
makeside(0,Start*4,0);
makeside(End*4-3,m+1,0);
makeside(End*4-2,m+1,0);
makeside(End*4-1,m+1,0);
makeside(End*4,m+1,0);
dijk();
cout< < < <<'\n';
return 0;}



转载地址:https://blog.csdn.net/li412302070/article/details/14108261 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:VIJOS 1792 摆花
下一篇:VIJOS 1605 双栈排序

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.191.171.39]2022年08月19日 01时54分39秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章