sdut原題鏈接
最短路徑問題 Time Limit: 1000MS Memory Limit: 65536KB
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
Hint
Author
以下為accepted代碼——Floyd
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#define INF 0x3f3f3f3fint x[104], y[104];double D[104][104];int main(){ int n, m, i, j, k, u, v, s, t; scanf("%d", &n); for(i = 0; i <= n; i++) { for(j = 0; j <= n; j++) { if(i == j) D[i][j] = 0; else D[i][j] = INF; } } for(i = 1; i <= n; i++) { scanf("%d %d", &x[i], &y[i]); } scanf("%d", &m); for(i = 1; i <= m; i++) { scanf("%d %d", &u, &v); if(D[u][v] > sqrt(pow(x[u]-x[v], 2) + pow(y[u]-y[v], 2))) D[u][v] = D[v][u] = sqrt(pow(x[u]-x[v], 2) + pow(y[u]-y[v], 2)); } for(k = 1; k <= n; k++) { for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { if(D[i][j] > D[i][k] + D[k][j]) D[i][j] = D[i][k] + D[k][j]; } } } scanf("%d %d", &s, &t); printf("%.2lf/n", D[s][t]); return 0;}/***************************************************User name: Result: AcceptedTake time: 4msTake Memory: 200KBSubmit time: 2017-02-17 21:11:24****************************************************/以下為accepted代碼——Dijkstra
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#define INF 0x3f3f3f3fdouble map[104][104], dist[104];int n, m;int x[104], y[104], vis[104];void Dijkstra(int v){ int i, j, k; for(i = 1; i <= n; i++)//dist數組的初始化 { dist[i] = map[v][i]; vis[i] = 0; } dist[v] = 0; vis[v] = 1; for(i = 0; i < n-1; i++) { int min = INF, u = v; for(j = 1; j <= n; j++)//尋找未標記結點的最小值 { if(vis[j] == 0 && dist[j] < min) { u = j; min = dist[j]; } } vis[u] = 1; for(k = 1; k <= n; k++)//更新最短路 { if(vis[k] == 0 && map[u][k] < INF && dist[k] > dist[u] + map[u][k]) { dist[k] = dist[u] + map[u][k]; } } }}int main(){ int i, j, u, v, s, t; scanf("%d", &n); memset(vis, 0, sizeof(vis)); for(i = 0; i <= n; i++) { for(j = 0; j <= n; j++) { if(i == j) map[i][j] = 0; else map[i][j] = INF; } } for(i = 1; i <= n; i++) { scanf("%d %d", &x[i], &y[i]); } scanf("%d", &m); for(i = 0; i < m; i++) { scanf("%d %d", &u, &v); if(map[u][v] > sqrt(pow(x[u]-x[v], 2) + pow(y[u]-y[v], 2))) map[u][v] = map[v][u] = sqrt(pow(x[u]-x[v], 2) + pow(y[u]-y[v], 2)); } scanf("%d %d", &s, &t); Dijkstra(s); printf("%.2lf/n", dist[t]); return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 196KBSubmit time: 2017-02-17 21:47:31****************************************************/新聞熱點
疑難解答
