在原来的上调一个最优化给一个关

数组

#include<bits/stdc++.h>
using namespace std;
const int N=114514;
double z,c[N];
int n,m,x,y,r,t,k,b[N],d[N],e[N],pre[N];
struct node
{
    double len;
    int from,to,next;
}a[N];
void add(int u,int v,double l)
{
    k++;
    a[k].from=u;
    a[k].to=v;
    a[k].len=l;
    a[k].next=pre[u];
    pre[u]=k;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>d[i]>>e[i];
    cin>>m;
    for(int i=1;i<=m;i++) cin>>x>>y,z=sqrt(((d[x]-d[y])*(d[x]-d[y]))+((e[x]-e[y])*(e[x]-e[y]))),add(x,y,z),add(y,x,z);
    cin>>r>>t;
    memset(c,127,sizeof(c));
    c[r]=0;
    for(int i=1;i<=n;i++)
    {
        int f=-1;
        for(int j=1;j<=n;j++) if(b[j]==0&&(f==-1||c[j]<c[f])) f=j;
        b[f]=1;
        for(int j=pre[f];j!=0;j=a[j].next)
        {
            int to=a[j].to;
            if(b[to]==0&&c[f]+a[j].len<c[to]) c[to]=c[f]+a[j].len;
        }
    }
    printf("%.2lf",c[t]);
}

队列

#include<bits/stdc++.h>
using namespace std;
const int N=114514;
double z,c[N];
int n,m,x,y,r,t,k,u,b[N],d[N],e[N],f[N],pre[N];
queue <int> q;
struct node
{
    int from,to,next;
    double len;
}a[N];
void add(int u,int v,double l)
{
    k++;
    a[k].from=u;
    a[k].to=v;
    a[k].len=l;
    a[k].next=pre[u];
    pre[u]=k;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>b[i]>>d[i];
    cin>>m;
    for(int i=1;i<=m;i++) cin>>x>>y,z=sqrt(((b[x]-b[y])*(b[x]-b[y]))+((d[x]-d[y])*(d[x]-d[y]))),add(x,y,z),add(y,x,z);
    cin>>r>>t;
    memset(c,127,sizeof(c));
    q.push(r);
    c[r]=0;
    f[r]=1;
    while(!q.empty())
    {
        u=q.front();
        for(int i=pre[u];i!=0;i=a[i].next)
        {
            int to=a[i].to;
            if(c[u]+a[i].len<c[to])
			{
                c[to]=c[u]+a[i].len;
                if(!f[to]) q.push(to);
            }
        }
        f[u]=0;
        q.pop();
    }
    printf("%.2lf",c[t]);
}