Think 求 最短 路徑問題。。 第一想到的就是 Floyd 算法， 所以就嘗試做了次。
PRoblem Description 平面上有n個點（n<=100），每個點的坐標均在-10000～10000之間。其中的一些點之間有連線。若有連線，則表示可從一個點到達另一個點，即兩點間有通路，通路的距離為兩點間的直線距離。現在的任務是找出從一點到另一點之間的最短距離。 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
#include<bits/stdc++.h>#define MAX 0x3f3f3f;using namespace std;struct node{ int x, y;}a[1050];double Floyd (int x, int y, int n);double sum (int a, int b);double Map[1050][1050];double dis[1050][1050];int main() { int i, j; int x, y, k; int A, B; int n; double ans; cin >> n; memset(Map, 0, sizeof(Map)); memset(dis, 0, sizeof(dis)); for (i = 1;i <= n;i ++) { for (j = 1;j <= n;j ++) { if (i == j) Map[i][j] = 0; else Map[i][j] = Map[j][i] = MAX; } } for (i = 1;i <= n ;i ++) { cin >> a[i].x >> a[i].y; } cin >> k; for (i = 1;i <= k;i ++) { cin >> A >> B; if (Map[A][B] > sum(a[A].x - a[B].x, a[A].y - a[B].y)) { Map[A][B] = sum(a[A].x - a[B].x, a[A].y - a[B].y); Map[B][A] = sum(a[A].x - a[B].x, a[A].y - a[B].y); } } cin >>x >> y; ans = Floyd(x, y , n); cout << fixed << setprecision(2) << ans << endl; //限制小數位數 return 0; } double Floyd (int x, int y, int n) { int i, j, k; for (i = 0;i <= n;i ++) { for (j = 0;j <= n;j ++) { dis[i][j] = Map[i][j]; } } for (k = 1;k <= n;k ++) { for (i = 1;i <= n;i ++) { for (j = 1;j <= n;j ++) { if (i != j) dis[i][j] = min(dis[i][j], dis[k][i] + dis[k][j]); } } } return dis[x][y]; } double sum (int a, int b) { return sqrt(a*a + b*b); }/***************************************************User name: Result: AcceptedTake time: 8msTake Memory: 17404KBSubmit time: 2017-02-20 09:40:29****************************************************/新聞熱點
疑難解答
