@[雨季](/space/show?uid=36728) A*本来靠的就是多次经过同一个点的距离改变，打标的话不就求不出来了吗？？？
by Brandon鹏 @ 2018-11-05 12:29:24
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
const double INF=1e9+7;
queue<int >q;
double dis[201];
int n,m;
double x[201],y[201];
int book[201];
struct node
{
int id;
double dis;
double g;
bool operator < (const node &bb)const
{
return dis+g>bb.dis+bb.g;
}
};
priority_queue<node>pq;
struct EDGE
{
int s;
int e;
double w;
int next;
}edge[100001];
int head[201];
int cnt;
void add(int s,int e,double w)
{
cnt++;
edge[cnt].s=s;
edge[cnt].e=e;
edge[cnt].w=w;
edge[cnt].next=head[s];
head[s]=cnt;
cnt++;
edge[cnt].s=e;
edge[cnt].e=s;
edge[cnt].w=w;
edge[cnt].next=head[e];
head[e]=cnt;
}
void spfa(int s)
{
for(int i=1;i<=n;i++)
{
dis[i]=INF;
}
dis[s]=0;
q.push(s);
book[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
book[u]=0;
for(int t=head[u];t;t=edge[t].next)
{
int v=edge[t].e;
if(dis[v]>dis[u]+edge[t].w)
{
dis[v]=dis[u]+edge[t].w;
if(!book[v])
{
book[v]=1;
q.push(v);
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&x[i],&y[i]);
}
for(int i=1;i<=m;i++)
{
int p1,p2;
scanf("%d%d",&p1,&p2);
add(p1,p2,sqrt((x[p2]-x[p1])*(x[p2]-x[p1])+(y[p1]-y[p2])*(y[p1]-y[p2])));
}
spfa(n);
node yes;
yes.id=1;
yes.dis=0;
yes.g=dis[1];
pq.push(yes);
int ti=0;
while(!pq.empty())
{
node now=pq.top();
pq.pop();
if(now.id==n)
{
ti++;
}
if(ti==2)
{
printf("%.2lf",now.dis);
return 0;
}
int u=now.id;
node tt;
for(int t=head[u];t;t=edge[t].next)
{
int v=edge[t].e;
tt.id=v;
tt.g=dis[v];
tt.dis=now.dis+edge[t].w;
pq.push(tt);
}
}
return 0;
}
```
by Brandon鹏 @ 2018-11-05 12:29:56
@[雨季](/space/show?uid=36728) 求教
by Brandon鹏 @ 2018-11-05 12:30:07
@[Brandon鹏](/space/show?uid=86154) 我也是这个问题,70分,但是如果加了它题解那个判重,连样例都过不去了.
by PPXppx @ 2019-09-18 20:20:38