%%%
by Vicssia @ 2019-01-28 16:50:34
我改了一下，现在输出102.8284，答案是202.8284.QAQ!```
#include<bits/stdc++.h>
//#define inf 0x3f3f3f3f
using namespace std;
double Dirt_Road,Rome_Road;
int tu[1050][1050]={0};
int n,tot=0;
double lu_dian[1050][2];
int head[50000];
queue <int>q;
struct lu_o
{
int x,next;
double z;
}e[10000];
void adde(int i,int l,double qwq)
{
e[tot].x=l;
e[tot].z=qwq;
e[tot].next=head[i];
head[i]=tot++;
}
double gougu_xian(int I,int L)
{
double r=(lu_dian[I][0]-lu_dian[L][0])*(lu_dian[I][0]-lu_dian[L][0])+(lu_dian[I][1]-lu_dian[L][1])*(lu_dian[I][1]-lu_dian[L][1]);
return sqrt(r);
}
double f[65435];
int vis[65435];
void Spfa()
{
f[1]=0;
q.push(1);
vis[1]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int k=head[u];k!=-1;k=e[k].next)
{
int p=e[k].x;
if(f[p]>f[u]+e[k].z)
{
f[p]=f[u]+e[k].z;
//printf("%d %.4lf\n",p,f[p]);
if(!vis[p])
{
q.push(p);
vis[p]=1;
}
}
}
}
///for(int i=1;i<=tot;i++)
//printf("%d %d %d %d %.4lf\n",i,e[i].x,e[i].next,head[i],e[i].z);
//for(int i=1;i<=tot;i++)printf("%.4lf\n",e[i].z);
//for(int i=1;i<=n+2;i++)
//printf("%.4lf ",f[i]);
printf("%.4lf",f[n+1]);
}
int main()
{
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
scanf("%lf%lf",&Dirt_Road,&Rome_Road);
scanf("%d",&n);
for(int i=1;i<=n+2;i++)
f[i]=99999999.0;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&lu_dian[i][0],&lu_dian[i][1]);
int I,L;
double qwq;
for(int i=1;;i++)
{
scanf("%d%d",&I,&L);
if(I==0&&L==0)break;
tu[I][L]=tu[L][I]=1;
qwq=gougu_xian(I,L);
qwq*=Rome_Road;
adde(I,L,qwq);
adde(L,I,qwq);
}
scanf("%lf%lf%lf%lf",&lu_dian[0][0],&lu_dian[0][1],&lu_dian[n+1][0],&lu_dian[n+1][1]);
for(int i=0;i<n+1;i++)
for(int l=0;l<=n+1;l++)
{
if(tu[i][l]==1)continue;
//if(i==l)continue;
qwq=gougu_xian(i,l);
qwq*=Dirt_Road;
adde(i,l,qwq);
adde(l,i,qwq);
tu[i][l]=tu[l][i]=1;
}
Spfa();
return 0;
}
```
by ILXC__SL @ 2019-01-28 16:56:58
抱歉，重发
```
#include<bits/stdc++.h>
//#define inf 0x3f3f3f3f
using namespace std;
double Dirt_Road,Rome_Road;
int tu[1050][1050]={0};
int n,tot=0;
double lu_dian[1050][2];
int head[50000];
queue <int>q;
struct lu_o
{
int x,next;
double z;
}e[10000];
void adde(int i,int l,double qwq)
{
e[tot].x=l;
e[tot].z=qwq;
e[tot].next=head[i];
head[i]=tot++;
}
double gougu_xian(int I,int L)
{
double r=(lu_dian[I][0]-lu_dian[L][0])*(lu_dian[I][0]-lu_dian[L][0])+(lu_dian[I][1]-lu_dian[L][1])*(lu_dian[I][1]-lu_dian[L][1]);
return sqrt(r);
}
double f[65435];
int vis[65435];
void Spfa()
{
f[1]=0;
q.push(1);
vis[1]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int k=head[u];k!=-1;k=e[k].next)
{
int p=e[k].x;
if(f[p]>f[u]+e[k].z)
{
f[p]=f[u]+e[k].z;
//printf("%d %.4lf\n",p,f[p]);
if(!vis[p])
{
q.push(p);
vis[p]=1;
}
}
}
}
///for(int i=1;i<=tot;i++)
//printf("%d %d %d %d %.4lf\n",i,e[i].x,e[i].next,head[i],e[i].z);
//for(int i=1;i<=tot;i++)printf("%.4lf\n",e[i].z);
//for(int i=1;i<=n+2;i++)
//printf("%.4lf ",f[i]);
printf("%.4lf",f[n+1]);
}
int main()
{
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
scanf("%lf%lf",&Dirt_Road,&Rome_Road);
scanf("%d",&n);
for(int i=1;i<=n+2;i++)
f[i]=99999999.0;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&lu_dian[i][0],&lu_dian[i][1]);
int I,L;
double qwq;
for(int i=1;;i++)
{
scanf("%d%d",&I,&L);
if(I==0&&L==0)break;
tu[I][L]=tu[L][I]=1;
qwq=gougu_xian(I,L);
qwq*=Rome_Road;
adde(I,L,qwq);
adde(L,I,qwq);
}
scanf("%lf%lf%lf%lf",&lu_dian[0][0],&lu_dian[0][1],&lu_dian[n+1][0],&lu_dian[n+1][1]);
for(int i=0;i<n+1;i++)
for(int l=0;l<=n+1;l++)
{
if(tu[i][l]==1)continue;
//if(i==l)continue;
qwq=gougu_xian(i,l);
qwq*=Dirt_Road;
adde(i,l,qwq);
adde(l,i,qwq);
tu[i][l]=tu[l][i]=1;
}
Spfa();
return 0;
}
```
by ILXC__SL @ 2019-01-28 16:57:38
救命啊！dalao救命啊！\QAQ/ ~ [键盘]
by ILXC__SL @ 2019-01-28 16:59:23
spfa开头定点为0
by ⚡LZSY01_XZY⚡ @ 2019-01-28 17:13:10
$\texttt{spfa开头顶点为0}$
by ⚡LZSY01_XZY⚡ @ 2019-01-28 17:15:57
@[LZSY01_XZY](/space/show?uid=141348) 改了，80分，QWQ.```
#include<bits/stdc++.h>
//#define inf 0x3f3f3f3f
using namespace std;
double Dirt_Road,Rome_Road;
int tu[1050][1050]={0};
int n,tot=0;
double lu_dian[1050][2];
int head[50000];
queue <int>q;
struct lu_o
{
int x,next;
double z;
}e[10000];
void adde(int i,int l,double qwq)
{
e[tot].x=l;
e[tot].z=qwq;
e[tot].next=head[i];
head[i]=tot++;
}
double gougu_xian(int I,int L)
{
double r=(lu_dian[I][0]-lu_dian[L][0])*(lu_dian[I][0]-lu_dian[L][0])+(lu_dian[I][1]-lu_dian[L][1])*(lu_dian[I][1]-lu_dian[L][1]);
return sqrt(r);
}
double f[65435];
int vis[65435];
void Spfa()
{
f[0]=0;
q.push(0);
vis[0]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int k=head[u];k!=-1;k=e[k].next)
{
int p=e[k].x;
if(f[p]>f[u]+e[k].z)
{
f[p]=f[u]+e[k].z;
//printf("%d %.4lf\n",p,f[p]);
if(!vis[p])
{
q.push(p);
vis[p]=1;
}
}
}
}
///for(int i=1;i<=tot;i++)
//printf("%d %d %d %d %.4lf\n",i,e[i].x,e[i].next,head[i],e[i].z);
//for(int i=1;i<=tot;i++)printf("%.4lf\n",e[i].z);
//for(int i=0;i<=n+2;i++)
//printf("%.4lf ",f[i]);
printf("%.4lf",f[n+1]);
}
int main()
{
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
scanf("%lf%lf",&Dirt_Road,&Rome_Road);
scanf("%d",&n);
for(int i=0;i<=n+2;i++)
f[i]=99999999.0;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&lu_dian[i][0],&lu_dian[i][1]);
int I,L;
double qwq;
for(int i=1;;i++)
{
scanf("%d%d",&I,&L);
if(I==0&&L==0)break;
tu[I][L]=tu[L][I]=1;
qwq=gougu_xian(I,L);
qwq*=Rome_Road;
adde(I,L,qwq);
adde(L,I,qwq);
}
scanf("%lf%lf%lf%lf",&lu_dian[0][0],&lu_dian[0][1],&lu_dian[n+1][0],&lu_dian[n+1][1]);
for(int i=0;i<n+1;i++)
for(int l=0;l<=n+1;l++)
{
if(tu[i][l]==1)continue;
//if(i==l)continue;
qwq=gougu_xian(i,l);
qwq*=Dirt_Road;
adde(i,l,qwq);
adde(l,i,qwq);
tu[i][l]=tu[l][i]=1;
}
Spfa();
return 0;
}
```
by ILXC__SL @ 2019-01-28 17:16:34
报歉，又重发
```
#include<bits/stdc++.h>
//#define inf 0x3f3f3f3f
using namespace std;
double Dirt_Road,Rome_Road;
int tu[1050][1050]={0};
int n,tot=0;
double lu_dian[1050][2];
int head[50000];
queue <int>q;
struct lu_o
{
int x,next;
double z;
}e[10000];
void adde(int i,int l,double qwq)
{
e[tot].x=l;
e[tot].z=qwq;
e[tot].next=head[i];
head[i]=tot++;
}
double gougu_xian(int I,int L)
{
double r=(lu_dian[I][0]-lu_dian[L][0])*(lu_dian[I][0]-lu_dian[L][0])+(lu_dian[I][1]-lu_dian[L][1])*(lu_dian[I][1]-lu_dian[L][1]);
return sqrt(r);
}
double f[65435];
int vis[65435];
void Spfa()
{
f[0]=0;
q.push(0);
vis[0]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int k=head[u];k!=-1;k=e[k].next)
{
int p=e[k].x;
if(f[p]>f[u]+e[k].z)
{
f[p]=f[u]+e[k].z;
//printf("%d %.4lf\n",p,f[p]);
if(!vis[p])
{
q.push(p);
vis[p]=1;
}
}
}
}
///for(int i=1;i<=tot;i++)
//printf("%d %d %d %d %.4lf\n",i,e[i].x,e[i].next,head[i],e[i].z);
//for(int i=1;i<=tot;i++)printf("%.4lf\n",e[i].z);
//for(int i=0;i<=n+2;i++)
//printf("%.4lf ",f[i]);
printf("%.4lf",f[n+1]);
}
int main()
{
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
scanf("%lf%lf",&Dirt_Road,&Rome_Road);
scanf("%d",&n);
for(int i=0;i<=n+2;i++)
f[i]=99999999.0;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&lu_dian[i][0],&lu_dian[i][1]);
int I,L;
double qwq;
for(int i=1;;i++)
{
scanf("%d%d",&I,&L);
if(I==0&&L==0)break;
tu[I][L]=tu[L][I]=1;
qwq=gougu_xian(I,L);
qwq*=Rome_Road;
adde(I,L,qwq);
adde(L,I,qwq);
}
scanf("%lf%lf%lf%lf",&lu_dian[0][0],&lu_dian[0][1],&lu_dian[n+1][0],&lu_dian[n+1][1]);
for(int i=0;i<n+1;i++)
for(int l=0;l<=n+1;l++)
{
if(tu[i][l]==1)continue;
//if(i==l)continue;
qwq=gougu_xian(i,l);
qwq*=Dirt_Road;
adde(i,l,qwq);
adde(l,i,qwq);
tu[i][l]=tu[l][i]=1;
}
Spfa();
return 0;
}
```
by ILXC__SL @ 2019-01-28 17:17:12
```cpp
f[1]=0;
q.push(1);
vis[1]=1;
```
这三句错了
应该是：
```cpp
f[0]=0;
q.push(0);
vis[0]=1;
```
by lyh0313 @ 2019-01-28 17:17:56
@[ILXC](/space/show?uid=79073) 你在用勾股定理求距离时，加个fabs()
by ⚡LZSY01_XZY⚡ @ 2019-01-28 17:21:22