#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define INF 1000000000 double G[110][110]; int axis[110][2]; int vis[110]; double d[110]; int n, m; int A, B; void dijkstra(){ memset(vis,0,sizeof(vis)); for(int i = 0;i <= n; i++)d[i] = INF; d[A] = 0; for(int i = 1;i <= n; i++){ int u = -1, MIN = INF; for(int j = 1;j <= n; j++){ if(vis[j]==0 && MIN > d[j]){ u = j; MIN = d[j]; } } if(u == B)return; vis[u] = 1; for(int v = 1;v <= n; v++){ if(vis[v]==0 && G[u][v] != 0 && d[v] > d[u] + G[u][v]){ d[v] = d[u] + G[u][v]; } } } } int main() { while(scanf("%d",&n) != EOF){ memset(G,0,sizeof(G)); for(int i = 1;i <= n; i++){ scanf("%d%d",&axis[i][0],&axis[i][1]); } scanf("%d",&m); while(m--){ int a, b; scanf("%d%d",&a,&b); double dis = sqrt((axis[a][0]-axis[b][0])*(axis[a][0]-axis[b][0]) + \ (axis[a][1]-axis[b][1])*(axis[a][1]-axis[b][1])); G[a][b] = G[b][a] = dis; } scanf("%d%d",&A,&B); dijkstra(); printf("%.2f\n",d[B]); } return 0; } /************************************************************** Problem: 2049 User: admin Language: C Result: Accepted Time:26 ms Memory:1240 kb ****************************************************************/