VIJOS 1119 Car的旅行路线-白红宇的个人博客

VIJOS 1119 Car的旅行路线

发布日期：2022-02-05 18:27:31 浏览次数：23 分类：技术文章

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

描述

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

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

格式

输入格式

第一行有四个正整数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
         
          
           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 双栈排序

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

描述

格式