SPFA 40分求助
查看原帖
SPFA 40分求助
494992
underline__jian楼主2022/2/13 19:49
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int N=1010;
int n,m,s,t,x[N],y[N],tot;
bool vis[N];
double dis[N];
struct node{
	int head,nxt,to;
	double c;
}e[N*N];
inline void add(int a,int b,double sq){
    e[++tot].to=b;
	e[tot].nxt=e[a].head;
	e[tot].c=sq;
	e[a].head=tot;
}
inline void spfa(int s){
    memset(dis,0x7f,sizeof(dis));
    dis[s]=0;
	vis[s]=true;
	queue<int> q;
    q.push(s);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=e[now].head;i;i=e[i].nxt)
            if(dis[e[i].to]>dis[now]+e[i].c){
                dis[e[i].to]=dis[now]+e[i].c;
                if(!vis[e[i].to]){
                    q.push(e[i].to);
                    vis[e[i].to]=1;
                }
            }
    }
}
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++){
        int a,b;
        scanf("%d%d",&a,&b);
        int xx=x[a]-x[b],yy=y[a]-y[b];
        add(a,b,sqrt(xx*1.0*xx*1.0+yy*1.0*yy*1.0));
        add(b,a,sqrt(xx*1.0*xx*1.0+yy*1.0+yy*1.0));
    }
    scanf("%d%d",&s,&t); 
    spfa(s);
    printf("%.2lf",dis[t]);
    return 0;
}

SPFA板子,不懂哪里错了

2022/2/13 19:49
加载中...