P1907 设计道路
题目描述
Caesar远征高卢回来后,对你大加赞赏,他亲自来到Genoa视察。
Genoa在你的建设下变得无比繁荣,由于财政收入的增加,你为城市修建了交通系统。古罗马的交通系统由两部分组成——Dirt Road和Rome Road。两个路口间只可能是其中一种道路。在Rome Road上可以驾驶马车,而在Dirt Road上则不行。由于修建道路是一项浩大的工程,使得你无法将整个城市用Rome Road连接起来。
现在Caesar已经到达码头,他要求去你家参观。Caesar由一个癖好,喜欢坐车而不喜欢走路。所以Caesar走Dirt Road时的不满值要比走Rome Road时大。
为了不让Caesar过于不满而罢免你的职位,请设计路线使得Caesar的不满值最小。
输入输出格式
输入格式:
输入数据第一行有两个实数,分别表示走Dirt Road和Rome Road一个单位长度时Caesar的不满值。接下来是一个整数N(N<=1000),代表路口总数。接下来有N行,每行一组实数(x,y)分别描述这N个路口的坐标。接下来有若干行,每行一组整数(i,j),表示第i个路口与第j个路口间为Rome Road,以0 0结束。最后两行,每行一对实数,分别描述码头和你家的坐标。
输出格式:
输出Caesar从码头到你家的最小不满值,保留4位小数
输入输出样例
输入样例#1:
100.0 2.0 2 1.0 0.0 2.0 1.0 1 2 0 0 0.0 0.0 2.0 2.0
输出样例#1:
202.8284 最短路什么鬼畜的操作、、、
再跑这一步的时候必须要分开写,否则出错?!
++n;scanf("%lf%lf",&x[n],&y[n]);
注意数组大小!
#include<cmath> #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 5010 #define maxn 9999999 using namespace std; queue<int>q; bool vis[N]; ]; double a,b,z,dis[N],x[N],y[N],f[N][N]; int read() { ,f=; char ch=getchar(); ;ch=getchar();} +ch-',ch=getchar(); return x*f; } struct Edge { int to,next; }edge[N*]; int add(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=head[x]; head[x]=tot; } int spfa(int s) { ;i<=n;i++) dis[i]=maxn,vis[i]=; vis[s]=,q.push(s); while(!q.empty()) { xx=q.front();q.pop();vis[xx]=false; for(int i=head[xx];i;i=edge[i].next) { int to=edge[i].to; if(dis[to]>dis[xx]+f[xx][to]) { dis[to]=dis[xx]+f[xx][to]; if(!vis[to]) vis[to]=true,q.push(to); } } } } int main() { scanf("%lf%lf",&a,&b); n=read();; ;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]); ) { xx=read(),yy=read(); add(xx,yy),add(yy,xx); &&yy==) break; z=sqrt(pow(x[xx]-x[yy],)+pow(y[xx]-y[yy],)); f[xx][yy]=f[yy][xx]=z*b; } ;i<=n;i++) ;j<=n;j++) if(!f[i][j]) { add(i,j),add(j,i); z=sqrt(pow(x[i]-x[j],)+pow(y[i]-y[j],)); f[i][j]=f[j][i]=z*a; } while(m--) { ++n; scanf("%lf%lf",&x[n],&y[n]); ;i<n;i++) { add(n,i),add(i,n); z=sqrt(pow(x[i]-x[n],)+pow(y[i]-y[n],)); f[n][i]=f[i][n]=z*a; } } spfa(n-); printf("%.4lf",dis[n]); ; }