VIJOS 1119 Car的旅行路线

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

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

就当Dijk的模板题了 

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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<iomanip>
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<i:a1.d<d;
}
};
priority_queue<self>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<<fixed<<setprecision(2)<<d[m+1]<<'n';
return 0;
}

最后

以上就是高兴巨人为你收集整理的VIJOS 1119 Car的旅行路线的全部内容，希望文章能够帮你解决VIJOS 1119 Car的旅行路线所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。