初学SPFA,40分求助qwq
查看原帖
初学SPFA,40分求助qwq
288716
lzqy_楼主2020/5/13 19:37
#include <bits/stdc++.h>
using namespace std;
vector<int>v[101];
vector<double>w[101];
queue<int>q;
pair<int,int>p[101];
int n,m,s,t;
double d[101];
bool k[101];
int len[101];
inline int read()                        
{
  int x=0;
  char c=getchar();
  for(; c<'0'  || c>'9';  c=getchar());
  for(; c<='9' && c>='0'; c=getchar())
    x=(x<<3)+(x<<1)+c-'0';               
  return x;
}
void SPFA()
{
  for(int i=1; i<=n; i++)
    d[i]=INT_MAX;
  d[s]=0;
  q.push(s);
  k[s]=1;
  while(!q.empty())
  {
    for(int i=0; i<len[q.front()]; i++)
    {
      if(d[v[q.front()][i]]>d[q.front()]+w[q.front()][i])
      {
        d[v[q.front()][i]]=d[q.front()]+w[q.front()][i];
        if(k[v[q.front()][i]]==0)
          q.push(v[q.front()][i]),k[v[q.front()][i]]=1;
      }
    }
    k[q.front()]=0;
    q.pop();
  }
  cout<<setprecision(2)<<fixed<<d[t];
}
int main()
{
  int x,y;
  double z;
  cin>>n;
  for(int i=1; i<=n; i++)
    p[i].first=read(),p[i].second=read();
  cin>>m;
  while(m--)
  {
    x=read(),y=read();
    v[x].push_back(y);
    v[y].push_back(x);
    len[y]++;
    len[x]++;
    z=(double)sqrt((p[x].first-p[y].first)*(p[x].first-p[y].first)+(p[x].second-p[y].second)*(p[x].second-p[y].second));
    w[x].push_back(z);
    w[y].push_back(z);
  }
  cin>>s>>t;
  SPFA();
  return 0;
}

WA前三个点,大佬求助TAT

2020/5/13 19:37
加载中...