T1342 最短路径问题

题目链接

思路
这题跟模板题一样的，只是图的权值要自己去算。代码如下：
对Floyd不懂的可以看以下这篇文章

#include<iostream>
#include<iomanip>      
#include<algorithm>
#define N 10001
#define INF 0x3f3f3f3f
using namespace std;
int x[N], y[N];	//用来存储每个点的x,y坐标
double g[N][N];	//用来记录点之间的距离
double calculate(int x1, int y1, int x2, int y2)
{//计算两点之间距离
	return sqrt((double)(x1 - x2)*(x1 - x2) + (double)(y1 - y2)*(y1 - y2));
}
int main()
{
	int n, m;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> x[i] >> y[i];
	cin >> m;
	for (int i = 1; i <= n; i++)//先初始化图表
	{
		for (int j = 1; j <= n; j++)
		{
			g[i][j] = INF;
			g[j][i] = INF;
		}
		g[i][i] = 0;
	}
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v; //这里读入那几点之间相连，并计算其距离，存入图中
		double temp = calculate(x[u], y[u], x[v], y[v]);
		g[u][v] = temp;
		g[v][u] = temp;
	}

	for (int k = 1; k <= n; k++)//Floyd算法核心
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (i != k && j != i && j != k && g[i][j] > g[i][k] + g[k][j])
					g[i][j] = g[i][k] + g[k][j];
	int u, v;
	cin >> u >> v;//C++的控制小数输出的格式
	cout << setiosflags(ios::fixed) << setprecision(3) << g[u][v] << endl;
	return 0;
}