think: 1注意重復(fù)邊的覆蓋 2注意map數(shù)組的初始化 3注意dist數(shù)組的初始化
sdut原題鏈接
圖結(jié)構(gòu)練習(xí)——最短路徑 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 給定一個(gè)帶權(quán)無(wú)向圖，求節(jié)點(diǎn)1到節(jié)點(diǎn)n的最短路徑。
Input 輸入包含多組數(shù)據(jù)，格式如下。 第一行包括兩個(gè)整數(shù)n m，代表節(jié)點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)。(n<=100) 剩下m行每行3個(gè)正整數(shù)a b c，代表節(jié)點(diǎn)a和節(jié)點(diǎn)b之間有一條邊，權(quán)值為c。
Output 每組輸出占一行，僅輸出從1到n的最短路徑權(quán)值。（保證最短路徑存在）
Example Input 3 2 1 2 1 1 3 1 1 0
Example Output 1 0
Hint
Author 趙利強(qiáng)
以下為accepted代碼
#include <iostream>#include <stdio.h>#include <string.h>using namespace std;#define INF 0x3f3f3f3fint n, m;int map[104][104], vis[104], dist[104];void Dijkstra(int v){ int i, j, k; for(i = 1; i <= n; i++)//dist數(shù)組的初始化 { 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++)//尋找未標(biāo)記結(jié)點(diǎn)的最小值 { 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, a, b, c; while(scanf("%d %d", &n, &m) != EOF) { memset(vis, 0, sizeof(vis)); for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { if(i == j) map[i][j] = 0; else map[i][j] = INF; } } for(i = 0; i < m; i++) { scanf("%d %d %d", &a, &b, &c); if(map[a][b] > c)///避免覆蓋最短路 map[a][b] = map[b][a] = c; } if(m == 0) printf("0/n"); else { Dijkstra(1); printf("%d/n", dist[n]); } } return 0;}/***************************************************User name: Result: AcceptedTake time: 12msTake Memory: 208KBSubmit time: 2017-02-17 19:30:41****************************************************/以下為wrong answer代碼——Dijkstra算法理解不扎實(shí)，導(dǎo)致變量位置使用錯(cuò)誤（將u的位置寫(xiě)成了v）
#include <iostream>#include <stdio.h>#include <string.h>using namespace std;#define INF 0x3f3f3f3fint n, m;int map[104][104], vis[104], dist[104];void Dijkstra(int v){ int i, j, k; for(i = 1; i <= n; i++)//dist數(shù)組的初始化 { 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++)//尋找未標(biāo)記結(jié)點(diǎn)的最小值 { 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[v][k] < INF && dist[k] > dist[u] + map[u][v]) { dist[k] = dist[u] + map[u][k]; } } }}int main(){ int i, j, a, b, c; while(scanf("%d %d", &n, &m) != EOF) { memset(vis, 0, sizeof(vis)); for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { if(i == j) map[i][j] = 0; else map[i][j] = INF; } } for(i = 0; i < m; i++) { scanf("%d %d %d", &a, &b, &c); if(map[a][b] > c)///避免覆蓋最短路 map[a][b] = map[b][a] = c; } if(m == 0) printf("0/n"); else { Dijkstra(1); printf("%d/n", dist[n]); } } return 0;}/***************************************************User name: Result: Wrong AnswerTake time: 16msTake Memory: 208KBSubmit time: 2017-02-17 19:27:15****************************************************/以下為wrong answer代碼—— 1 沒(méi)有考慮到重復(fù)邊的覆蓋問(wèn)題 2 map數(shù)組初始化錯(cuò)誤
#include <stdio.h>#include <string.h>#define INF 9999999int n, m;int map[104][104], dist[10400], vis[10400];void Dijkstra(int v){ for(int i = 1; i <= n; i++) { dist[i] = map[v][i]; vis[i] = 0; } vis[v] = 1; dist[v] = 0; for(int i = 0; i < n-1; i++) { int min = INF, u = v; for(int j = 1; j <= n; j++)//尋找未訪問(wèn)的結(jié)點(diǎn)中的最小值 { if(vis[j] == 0 && dist[j] < min) { u = j; min =dist[j]; } } vis[u] = 1; for(int 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 a, b, c; while(scanf("%d %d", &n, &m) != EOF) { memset(map, 0, sizeof(map)); memset(vis, 0, sizeof(vis)); for(int i = 0; i < m; i++) { scanf("%d %d %d", &a, &b, &c); map[a][b] = c; } Dijkstra(1); printf("%d/n", dist[n]); } return 0;}/***************************************************User name: Result: Wrong AnswerTake time: 12msTake Memory: 192KBSubmit time: 2017-02-17 18:41:44****************************************************/新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
