데이터 구조 - pta - 최 단 경로 (Dijkstra) + 출력 경로

① 이 문 제 는 변 과 상 관 없 이 인접 표 가 적용 되 지 않 고 심지어 1 차원 배열 만 인접 행렬 을 사용 하지 않 는 다.
② 다 원 최 단 로 의 Dijkstra 표기 법 은 보조 변수 판단 이 많아 서 첫 번 째 점프 가 가장 가 까 워 질 수 있 도록 순 서 → 욕심
③ Dijkstra 구 조 → while → 초기 화 → for 최소 값 찾기 → 인접 업데이트, vis
오래된 영화 '007 의 생사 의 고비' (Live and Let Die) 에서 007 이 마 약사 범 에 게 악어 못 중심의 작은 섬 에 잡 혀 그 는 아주 대담 한 방법 으로 탈출 했다. 연못 속 악어 들 의 큰 머리 를 밟 고 해안 으로 뛰 어 올 랐 다!(그 당시 스턴트맨 이 마지막 악어 에 게 발 을 물 렸 다 고 하 는데 다행히 두 꺼 운 장 화 를 신고 도 망 쳤 다.)
악어 풀 을 설치 하면 길이 가 100 미터 인 사각형 이 고 중심 좌 표 는 (0, 0) 이 며 동북 각 좌 표 는 (50, 50) 이다.지심 도 는 (0, 0) 을 원심 으로 하고 지름 15m 의 원 이다.연못 에 분포 되 어 있 는 악어 의 좌표 와 007 번 점프 할 수 있 는 최대 거 리 를 정 해 야 한다. 그 에 게 가장 짧 은 탈출 경 로 를 알려 줘 야 한다. 이른바 '최 단' 은 007 번 점프 할 걸음 수가 가장 적은 것 을 말한다.
입력 형식:
우선 첫 줄 에 두 개의 정수: 악어 수량 을 드 립 니 다. N (≤) 과 007 회 점프 가능 한 최대 거리 D。뒤이어 N 좋아, 줄 마다 악어 한 마 리 를 줘. ( 좌표. 주의: 악어 두 마리 가 같은 점 에 있 지 않 습 니 다.
출력 형식:
007 탈출 이 가능 하 다 면 먼저 첫 줄 에서 007 을 수출 하려 면 점프 의 최소 걸음 수 를 필요 로 하 며, 두 번 째 줄 부터 지심 도 에서 해안 까지 한 걸음 한 걸음 뛰 어야 하 는 악어 좌 표를 제시 해 야 한다. (. 탈출 이 불가능 하 다 면 첫 줄 에서 0 을 점프 걸음 수로 출력 합 니 다. 최 단 경로 가 유일 하지 않 으 면 첫 번 째 점프 의 가장 가 까 운 해 를 출력 합 니 다. 문 제 는 이러한 해 가 유일 하 다 는 것 을 보증 합 니 다.
입력 샘플 1:

17 15
10 -21
10 21
-40 10
30 -50
20 40
35 10
0 -10
-25 22
40 -40
-30 30
-10 22
0 11
25 21
25 10
10 10
10 35
-30 10

출력 예시 1:

4
0 11
10 21
10 35

입력 샘플 2:

4 13
-12 12
12 12
-12 -12
12 -12

출력 예시 2:

0

#include 
using namespace std;

bool vis[105]; 
int shortd[105];
int Path[105];//Dijkstra        
int res=INT_MAX;//     
int cnt[105];//     

struct point1  //   
{
	double x;
	double y;
};

struct fj1    //              ，         
{
	double d;
	int index;
};

struct Graph
{
	point1 point[105];
	fj1 fj[105];
	int c[105][105];//    ，           
	int n,edge;
	double D;     //       
};

bool cmp(fj1 a,fj1 b)//      
{
	return a.d=50||(abs(G.point[j].y)+G.D>=50))
		{

		if(res>shortd[j])//          
		{
			//       
			res=shortd[j];
			//     
			int size=0;
			int temp=j;

			for(int z=0;z>G.n>>G.D;

for(int i=0;i>G.point[i].x>>G.point[i].y;
	G.fj[i].d= sqrt((G.point[i].x)*(G.point[i].x)+(G.point[i].y)*(G.point[i].y));
	G.fj[i].index=i; //     ，     ，    
	
}
sort(G.fj,G.fj+G.n,cmp);//             
for(int i=0;i=0;i--)//Path      ，       
	{
		cout<