最短距离问题（Dijkstra算法）
题目链接：
https://begin.lydsy.com/JudgeOnline/problem.php?cid=1318&pid=10
同样的题哈，不一样的解法，也总算是学了Dijkstra了。
[送上一句迟到的祝福：新春快乐]
Problem K: 最短路径问题
Time Limit: 1 Sec Memory Limit: 128 MB
Description
平面上有n个点（n<=100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
Input
共n+m+3行，其中:
第一行为整数n。
第2行到第n+1行（共n行），每行两个整数x和y，描述了一个点的坐标。
第n+2行为一个整数m，表示图中连线的个数。
此后的m行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。
最后一行：两个整数s和t，分别表示源点和目标点。
Output
仅一行，一个实数（保留两位小数），表示从s到t的最短路径长度。
Sample Input
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
Sample Output
3.41
HINT
1.题目分析
略 [若还不了解此模板题，请去吐槽本蒟蒻博客最短路（Floyed-Warshall）]
好了，进入正题：
1. 首先了解一下Dijkstra：
Dijkstra算法 O（N2）
用来计算从一个点到其他所有点的最短路径的算法，是一种单源最短路径算法，也就是说，只能计算起点只有一个的情况。[书上原话]
同样不能处理负边权。
2. 算法描述：
设起点为s，dis[v]表示从s到v的最短路径，pre[v]为v的前驱节点，用来输出路径，n为总点个数。
（a）初始化：dis[v]=∞(v≠s,显然到起点距离不可能为∞)；dis[s]=0(到起点距离为0);pre[s]=0;(起点没有前驱)
（b）for i=1 to (n or n-1) do
①在没有被访问的点中找一个顶点u使得dis[u]最小；
(PS:因为你的开头不小，后面自然就会大，有点像贪心)
②将u标记为当前已确定最短路径；(这里不能太目光短浅)
③
for v=1 to n do
//这里就是为了避免目光短浅，每个点都枚举，因为当前只有u为已确定最短路径，其它点都可能被u所修改
if (dis[v]>dis[u]+dis[u][v])
{
dis[v]>dis[u]+dis[u][v]；
//枚举以u为“中转点”的未确定最短路径的点v
pre[v]=u;
//更新前驱点
}
（c）算法结束，dis[v]为s到v的最短距离，pre[v]为v的前驱点，用来输出路径。
3. 算法分析&实例讲解：
1.我们的Dijkstra也是与Floyed差不多，运用“中转点”的思想，但不同的是，我们把起点s也作为一个特殊的“中转点”，而且我们是一步一步往后推最短路。
显然我们可以知道，从s到t的最短路径上，必先经过一个“中转点”v，那么我们在求出到t的最短路时，必先确定到v的最短路，换句话说：
如果起点到某一点v的最短路要经过v0，那么其“中转点”v0一定是于v确定了的最短路径点。
[是不是很绕，没关系，我们画个样例就清楚了。]
2.实例
我们把所有的点分成两类：
1.已确定最短路的点（true）
2.未确定的点（false）
那么每一次在求出一个点的最短路时，就是将一个false变为true，而且这个false点的中转点必须是true(必须前面的路径最短，才能使后面延续前面的状态)。
这里有一句很重要的话：
每一个终点都会被它的最后一个中转点所修改，求得最短路。
好了，我们来做一番模拟：
Begin
dis[s]=0,dis[p]=0x7fffffff(p!=s)；
PS:s为出发点，默认为1。
Step 1：
找到dis[1]最小，将1变为true，同时用1向其它所有false点做出修改：
dis[2]=2,dis[3]=4,dis[4]=7;
HINT:此时2,3,4点被它的最后一个中转点1修改了最短路径。
Step 2:
找到dis[2]最小，将2变为tue，同时用2向其它所有false点做出修改：
dis[3]=3,dis[5]=4;
HINT:此时3,5点被它的最后一个中转点2修改了最短路径。
Step 3:
找到dis[3]最小，将3变为tue，同时用3向其它所有false点做出修改：
dis[4]=4(修不修改无所谓);
注意：这里dis[5]被3修改为9，大于4，所以不做修改。
HINT:此时4点被它的最后一个中转点3修改了最短路径。
Step 4:
找到dis[4]最小，将4变为tue，同时用4向其它所有false点做出修改：
没有点可以被4修改为更小的最小路径。
HINT:此时没有点被它的最后一个中转点4修改了最短路径。
Step 5:
找到dis[5]最小，将5变为tue，同时用5向其它所有false点做出修改：
没有点可以被5修改为更小的最小路径。
HINT:此时没有点被它的最后一个中转点5修改了最短路径。
End
即可求出起点到任一点的最短距离。
代码实现：
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int n,m;
bool vis[101]; //vis表示当前点是否被访问
int x[101],y[101]; //依据题意的坐标
double dis[101],w[101][101]; //dis表示最短距离，w用邻接矩阵方式存储边
inline void read(int &x) //quickly_read 快读
{
x=0;bool f=true;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=false;ch=getchar();}
while (ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x= f==true? x:~x+1;
}
int main()
{
read(n);
for (int i=1;i<=n;i++)
read(x[i]),read(y[i]);
read(m);
int a,b,s,t;
memset(w,0x7f,sizeof(w));
//初始化，即任两点间都未有边，PS:注意memset按字节赋值，故为0x7f==127
while (m--)
{
read(a),read(b);
w[a][b]=w[b][a]=sqrt(pow(x[a]-x[b],2)+pow(y[a]-y[b],2));
//无向图注意，两个方向都要赋值
}
read(s),read(t);
for (int i=1;i<=n;i++) dis[i]=w[s][i];
//根据起点来对其它点的最短距离来相应赋值
dis[s]=0,vis[s]=true;
//将起点打上标记，表示已访问，且到起点的最短路为0
double min; //记录当前找到的false点的最短距离
int u; //记录当前找到的false点
for (int i=1;i<n;i++) //1 to n OR 1 to n-1都没关系，起点可看作已访问
{
min=1e9,u=0; //min,u初始化
for (int j=1;j<=n;j++)
if (!vis[j]&&min>dis[j]) u=j,min=dis[j];
//寻找未被访问点且此时到j点的距离最短，进行赋值
if (!u) break; //如果u值未被改变，则整个图都已被访问
vis[u]=true; //标记已访问
for (int v=1;u!=v&&v<=n;v++) //枚举其它点，且不与自身重合
if (dis[v]>dis[u]+w[u][v]) dis[v]=dis[u]+w[u][v];
//到v的目前最短路大于到中转点u的距离+u到v的边长，则更新
}
printf("%.2f",dis[t]);
return 0;
}