SSL-ZYC 采购特价商品【SPFA】-白红宇

SSL-ZYC 采购特价商品【SPFA】

阅读量：5148 次

发布时间：2019-06-13

本文共 1762 字，大约阅读时间需要 5 分钟。

题目大意：

给出每个点的坐标，求出

SS到

TT的最短路。

InputInput

50 02 02 20 23 151 21 31 42 53 51 5

Outout

3.41

思路：

n⩽100，

FloydFloyd，

DijkstraDijkstra和

SPFASPFA都可以轻松跑过。

先用勾股求出有连边的点之间的距离，双向存边，再跑一便最短路即可。

这道题是无向图而不是有向图！

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const double inf=99999999;int vis[501],head[501],n,m,x[501],y[501],s,t,k,X,Y;double dis[501];struct edge  {    int next,to;    double dis;  //边长是实数}e[50001];double Dis(int xx,int yy)  //勾股求距离{    return sqrt((double)(x[xx]-x[yy])*(x[xx]-x[yy])+(y[xx]-y[yy])*(y[xx]-y[yy]));}void add(int from,int to,double Dis)  //建图{    k++;    e[k].next=head[from];    e[k].dis=Dis;    e[k].to=to;    head[from]=k;}void spfa()  {    queue
        
          q;  //队列，orz手写队列的dalao    for (int i=1;i<=n;i++)  //初始化    {        vis[i]=0;        dis[i]=inf;    }    q.push(s);  //插入起始点    vis[s]=1;    dis[s]=0;    while (q.size())  //相当于 while(!q.empty())    {        int u=q.front();  //取出队首        q.pop();  //弹出        vis[u]=0;        for (int i=head[u];i;i=e[i].next)  //邻接表        {            int v=e[i].to;            if (dis[v]>dis[u]+e[i].dis)  //更新最短路            {                dis[v]=dis[u]+e[i].dis;                if (!vis[v])                {                    vis[v]=1;                    q.push(v);  //入队                }            }        }    }}int main(){    scanf("%d",&n);    for (int i=1;i<=n;i++)      scanf("%d%d",&x[i],&y[i]);    scanf("%d",&m);    for (int i=1;i<=m;i++)    {        scanf("%d%d",&X,&Y);        add(X,Y,Dis(X,Y));        add(Y,X,Dis(X,Y));  //无向图，建两次边    }    scanf("%d%d",&s,&t);    spfa();    printf("%0.2lf\n",dis[t]);    return 0;}