0
已解决
李庚午
中级守护
中级守护
酷町堂P2484 洛谷P1491
真是莫名其妙,代码逻辑是没有任何问题的,样例也能过,偏偏一提交就是全部输出0.00,求解决。
#include<bits/stdc++.h>
using namespace std;
const int maxn=207;
const double inf=999999999;
struct point
{
int x,y;
}points[maxn];
double G[maxn][maxn];
double dis[maxn];
int n,m,s,pre[maxn],pr[maxn];
double dist(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void dijkstra()
{
fill(dis+1,dis+n+1,inf);dis[1]=0;
bool vis[maxn];memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)
{
int v=-1;
for(int j=1;j<=n;j++)
if ((v==-1||dis[j]<dis[v])&&(!vis[j])) v=j;
if (v==-1) break;
vis[v]=true;
for(int j=1;j<=n;j++)
{
if (!vis[j]&&G[v][j]!=inf&&dis[j]>dis[v]+G[v][j])
{
dis[j]=dis[v]+G[v][j];
pre[j]=v;
}
}
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
points[i]=(point){x,y};
}
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d %d",&u,&v);
G[u][v]=dist(points[u],points[v]);
G[v][u]=dist(points[u],points[v]);
}
dijkstra();
memcpy(pr,pre,sizeof(pre));
int now=n;
double ans=inf;
while(pr[now])
{
double w=G[now][pr[now]];
G[now][pr[now]]=inf;
G[pr[now]][now]=inf;
dijkstra();
if (dis[n]<ans) ans=dis[n];
G[now][pr[now]]=w;
G[pr[now]][now]=w;
now=pr[now];
}
if (ans==inf) printf("-1");
else printf("%.2f",ans);
return 0;
}
附评测记录:鼠标移到WA色块上可以看到全部输出的都是0.00
李庚午在2018-07-15 18:48:39追加了内容