记录编号 |
50692 |
评测结果 |
AAAAA |
题目名称 |
[省常中2011S4] 最短路径问题 |
最终得分 |
100 |
用户昵称 |
cstdio |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.002 s |
提交时间 |
2012-11-28 20:28:17 |
内存使用 |
0.40 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
using namespace std;
const double MAX=0xffffff;
double c[101][101]={0},point[101][2]={0},f[101]={0};//c为路程,point为点,f为到当前最短路
bool used[101]={0};
int n,m,s,t;//n为顶点数,s起点t终点
void Dijkstra(void){
int i,sum,min=-1;
for(i=1;i<=n;i++) f[i]=c[s][i];
used[s]=1,sum=1;
while(sum<n){
min=-1;
for(i=1;i<=n;i++){
if(used[i]) continue;
if(min==-1||f[i]<f[min]) min=i;
}
if(min==-1) break;
sum++;
used[min]=1;
for(i=1;i<=n;i++){
if(used[i]) continue;
if(f[min]+c[min][i]<f[i]) f[i]=f[min]+c[min][i];
}
}
}
int main(){
freopen("short.in","r",stdin);
freopen("short.out","w",stdout);
cout<<setiosflags(ios::fixed)<<setprecision(2);
scanf("%d",&n);
int i,j,k;
double x,y;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(i==j) continue;
c[i][j]=MAX;
}
}
for(i=1;i<=n;i++) scanf("%lf%lf",&point[i][0],&point[i][1]);
scanf("%d",&m);
for(k=0;k<m;k++){
scanf("%d%d",&i,&j);
x=point[i][0]-point[j][0],y=point[i][1]-point[j][1];
c[i][j]=sqrt(x*x+y*y),c[j][i]=c[i][j];
}
scanf("%d%d",&s,&t);
Dijkstra();
cout<<f[t]<<endl;
return 0;
}