Time Limit: 1000MS Memory Limit: 65536KB
平面上有n個點（n<=100），每個點的坐標均在-10000～10000之間。其中的一些點之間有連線。若有連線，則表示可從一個點到達另一個點，即兩點間有通路，通路的距離為兩點間的直線距離?，F在的任務是找出從一點到另一點之間的最短距離。
Input
第1行為整數n。 第2行到第n+1行（共n行），每行兩個整數x和y，描述了一個點的坐標（以一個空格分隔）。 第n+2行為一個整數m，表示圖中連線的個數。 此后的m行，每行描述一條連線，由兩個整數i和j組成，表示第1個點和第j個點之間有連線。 最后一行：兩個整數s和t，分別表示源點和目標點。
Output
僅1行，一個實數（保留兩位小數），表示從s到t的最短路徑長度。
Example Input
5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5
Example Output
3.41
Hint
本題和 SDUT 2143 圖結構練習——最短路徑（http://blog.csdn.net/yxc9806/article/details/55522586） 基本完全一致，變化無非是源點和目標點改變了，邊長需要求出罷了。
Submit
#include <bits/stdc++.h>#define INF 9999999.9using namespace std;const int MAXN = 110;struct node{ double x, y;}n[MAXN];int N, S, T, i, j, k;double mp[MAXN][MAXN];bool visit[MAXN];double dist[MAXN];void dijkstra(){ memset(visit, 0, sizeof(visit)); for(i = 0; i <= N; i++) { dist[i] = mp[i][S]; } visit[S] = 1; dist[S] = 0; for(i = 1; i <= N; i++) { double Min = INF; for(j = 1; j <= N; j++) { if(!visit[j] && dist[j] < Min) { Min = dist[j]; k = j; } } visit[k] = 1; for(j = 1; j <= N; j++) if(!visit[j] && mp[k][j] < INF) if(dist[k] + mp[k][j] < dist[j]) dist[j] = dist[k] + mp[k][j]; } printf("%.2lf/n", dist[T]);}int main(){ memset(mp, INF, sizeof(mp)); scanf("%d", &N); for(i = 1; i <= N; i++) scanf("%lf %lf", &n[i].x, &n[i].y); int M; scanf("%d", &M); double l, x, y; while(M--) { scanf("%d %d", &i, &j); x = n[i].x - n[j].x; y = n[i].y - n[j].y; l = sqrt(x*x+y*y); mp[i][j] = mp[j][i] = l; } for(i = 0; i < MAXN; i++) mp[i][i] = 0; scanf("%d %d", &S, &T); dijkstra(); return 0;}新聞熱點
疑難解答
