Dijkstra模板

队列实现

#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]);
}

哈哈，我抢到888888了