HDu最短経路問題

問題C:最短パス問題
時間制限:1 Sec
メモリ制限:128 MB
コミット:5
解決:5
[コミット][ステータス][ディスカッション]
タイトルの説明
平面上にはn個の点(n<=100)があり、各点の座標は-1000~10000の間にある.その中のいくつかの点の間には結線がある.結線があれば、ある点から別の点に到達できることを示す.すなわち、2点間に通路があり、通路の距離は2点間の直線距離である.現在の任務は、1点から別の点までの最短経路を見つけることである.
入力
ファイルn+m+3行を入力します.
第1の動作整数n.
2行目からn+1行目(共n行)まで、1行に2つの整数xとyがあり、1点の座標が記述されている.
n+2番目の動作は整数mであり、図中の連線の個数を表す.
その後のm行は、各行に1本の連線を記述し、2つの整数iとjからなり、i番目の点とj番目の点の間に連線があることを示す.
最後の行:ソースポイントとターゲットポイントを表す2つの整数sとt
しゅつりょく
出力ファイルは1行のみで、実数(小数2桁保持)はsからtまでの最短パス長を表します.
サンプル入力

5
0 0
2 0
2 2
0 2
3 1
5 
1 2 
1 3 
1 4 
2 5 
3 5 
1 5

サンプル出力

3.41

ベースの最短パスは、2点間の距離式を加えただけです.

#include
#include
#include
#include
#include
#include
using namespace std;
const double inf=0x3f3f3f3f;
int n,m;
double mat[105][105];//         
int vis[105];
double dis[105];
struct node{//     
	int x,y;
}s[105];
double Length(int a,int b){
	return sqrt((s[a].x -s[b].x )*(s[a].x -s[b].x )+(s[a].y -s[b].y )*(s[a].y -s[b].y ));
}
void Djk(int c,int d){
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
		dis[i]=mat[c][i];
	vis[c]=1;dis[c]=0;
	for(int i=0;idis[pos]+mat[pos][j])
				dis[j]=dis[pos]+mat[pos][j];
		}
	}
	printf("%.2lf
",dis[d]);
	return ;
}
int main()
{
	int a,b;
	scanf("%d",&n);
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			mat[i][j]=inf;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&s[i].x ,&s[i].y );
	scanf("%d",&m);
	for(int i=0;i