题目描述

Caesar远征高卢回来后，对你大加赞赏，他亲自来到Genoa视察。

Genoa在你的建设下变得无比繁荣，由于财政收入的增加，你为城市修建了交通系统。古罗马的交通系统由两部分组成——Dirt Road和Rome Road。两个路口间只可能是其中一种道路。在Rome Road上可以驾驶马车，而在Dirt Road上则不行。由于修建道路是一项浩大的工程，使得你无法将整个城市用Rome Road连接起来。

现在Caesar已经到达码头，他要求去你家参观。Caesar由一个癖好，喜欢坐车而不喜欢走路。所以Caesar走Dirt Road时的不满值要比走Rome Road时大。

为了不让Caesar过于不满而罢免你的职位，请设计路线使得Caesar的不满值最小。

原题链接

Solve

Dijkstra算法寻找最短路径

1.路口，码头，家都作为节点。节点0为码头，节点n+1为家（建图关键）。

2.跑一遍Dijkstra。

Tips

1.本题数据范围较小，可以用邻接矩阵

2.最大距离最好开大些，开0x3fff就WA了两个点，开1e6就A了

Code

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;  //标准开头
const int N=5000;
double m[N][N];  //邻接矩阵存边
int n;  //路口数
double e,r;  //e——Dirt Road，r——Rome Road
double x[N],y[N];  //节点信息
double d[N];  //离码头的最短距离
bool vis[N][N];  //vis[i][j]==true——i到j之间有Rome Road，false——没有
bool f[N];  //Dijkstra遍历时是否访问过，true——是，false——否
int dx,dy;  //dx到dy有Rome Road
int main()
{
	cin>>e>>r>>n;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	while(cin>>dx>>dy&&dx!=0&&dy!=0){  //建立Rome Road
		vis[dx][dy]=vis[dy][dx]=true;
		m[dx][dy]=m[dy][dx]=r*sqrt((x[dx]-x[dy])*(x[dx]-x[dy])+(y[dx]-y[dy])*(y[dx]-y[dy]));
	}
	cin>>x[0]>>y[0]>>x[n+1]>>y[n+1];
	for(int i=0;i<=n+1;i++){  //建立Dirt Road
		for(int j=0;j<=i;j++){ 
			if(!vis[i][j]) m[i][j]=m[j][i]=e*sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		}
	}
	d[0]=0;
	for(int i=1;i<=n+1;i++) d[i]=1e6;
	for(int i=0;i<=n+1;i++){  //核心Dijkstra
		int k;
		double maxn=1e6;
		for(int j=0;j<=n+1;j++){
			if(!f[j]&&d[j]<maxn){
				maxn=d[j];
				k=j;
			}
		}
		if(maxn==1e6) break;
		f[k]=true;
		for(int j=0;j<=n+1;j++){
			if(d[k]+m[k][j]<d[j]) d[j]=d[k]+m[k][j];
		}
	}
	printf("%.4lf",d[n+1]);  //完美输出
	return 0;
}