think: 1題目由題意可知輸入數據很大，而且頂點數達到了500000，如果用Dijkstra算法和Floyd算法定義的二維數組都無法達到500000*500000,因此可以考慮使用Bellma-Ford算法，不過得使用標記變量check用來標記數組dis在本輪松弛中是否發生了變化 2注意有權無向圖 3題意提示權值大于等于0，如果權值存在小于零，適合用Belloc-Ford算法或Bellman-Ford算法的隊列優化了 4反思：自己在t的變化上忽視了在每次循環中應使用兩次t++，導致了有效數據被覆蓋，數組一開始開小了，但自己感覺計算就應該是1<=n<=50000,1<=m<=200000，以后需要注意留心仔細一點 5嘗試推測題意考察點，把握重點，注意細節 6剛才又學習了SPFA算法，用SPFA算法實現了一下，可能因為后臺數據比較類型相似，兩種算法實現的時間差不多，可能自己因為剛學習，一些SPFA算法的優化還不會，自己想同樣加標記變量，結果可能加標記變量后一些位置重新松弛的時候變化不對，因此結果wrong answer，自己應該繼續深入學習，爭取學會SPFA算法很好的優化 7SPFA算法（Bellman-Ford算法的隊列優化） 8Floyd算法的時間復雜度為O(N^3),Dijkstra算法的時間復雜度為O((M + N)logN),堆優化的Dijkstra算法時間復雜度可以達到O(MlogN),而Bellman-Ford算法的時間復雜度為O(NM),隊列優化的Bellman-Ford算法時間復雜度最壞也是O(NM) 9Floyd算法和Dijkstra算法適合于稠密圖，和頂點關系密切,而Bellman-Ford算法與隊列優化的Bellman-Ford算法適合于稀疏圖，和邊關系密切
sdut原題鏈接
C–最短路 Time Limit: 7000MS Memory Limit: 65536KB
PRoblem Description 給出一個帶權無向圖，包含n個點，m條邊。求出s，e的最短路。保證最短路存在。
Input 多組輸入。 對于每組數據。 第一行輸入n，m(1<= n && n<=5*10^5,1 <= m && m <= 2*10^6)。 接下來m行，每行三個整數，u,v,w,表示u，v之間有一條權值為w(w >= 0)的邊。 最后輸入s，e。
Output 對于每組數據輸出一個整數代表答案。
Example Input 3 1 1 2 3 1 2
Example Output 3
Hint
Author zmx
以下為accepted代碼——Bellman-Ford
#include <stdio.h>#define INF 0x3f3f3f3fint dist[500004], u[4000004], v[4000004], w[4000004];int main(){ int n, m, i, k, s, e, check, flag, t, x, y, z; while(scanf("%d %d", &n, &m) != EOF) { t = 1; for(i = 1; i <= m; i++) { scanf("%d %d %d", &x, &y, &z); u[t] = x, v[t] = y, w[t] = z; t++; u[t] = y, v[t] = x, w[t] = z; t++;///注意：使用之后一定要+1 } scanf("%d %d", &s, &e); for(i = 1; i <= n; i++) dist[i] = INF; dist[s] = 0; m = 2*m;//有權無向圖 //Bellman-Ford算法核心語句 for(k = 0; k < n-1; k++) { check = 0; for(i = 1; i <= m; i++) { if(dist[v[i]] > dist[u[i]] + w[i]) { dist[v[i]] = dist[u[i]] + w[i]; check = 1; } } if(check == 0) break; } //檢測負權回路 flag = 0; for(i = 1; i <= m; i++) { if(dist[v[i]] > dist[u[i]] + w[i]) flag = 1; } if(flag) printf("error because of -/n"); else printf("%d/n", dist[e]); } return 0;}/***************************************************User name: Result: AcceptedTake time: 808msTake Memory: 36672KBSubmit time: 2017-02-19 16:33:18****************************************************/以下為accepted代碼——SPFA算法
#include <stdio.h>#include <string.h>#define INF 0x3f3f3f3fint tp, op;int book[500004], link[500004];int dist[500004], u[4000004], v[4000004], w[4000004];int main(){ int n, m, i, k, s, e, t, x, y, z; while(scanf("%d %d", &n, &m) != EOF) { tp = op = 0; memset(book, -1, sizeof(book)); memset(link, 0, sizeof(link)); t = 1; for(i = 1; i <= m; i++) { scanf("%d %d %d", &x, &y, &z); u[t] = x, v[t] = y, w[t] = z; t++; u[t] = y, v[t] = x, w[t] = z; t++; } scanf("%d %d", &s, &e); for(i = 1; i <= n; i++) dist[i] = INF; dist[s] = 0; m = 2*m; link[tp++] = v[s]; book[s] = 1; while(op < tp) { op++; k = link[op]; while(k <= m) { if(dist[v[k]] > dist[u[k]] + w[k]) { dist[v[k]] = dist[u[k]] + w[k]; if(book[k] == 0) { link[tp++] = v[k]; book[v[k]] = 1; } } k++; } } printf("%d/n", dist[e]); } return 0;}/***************************************************User name: Result: AcceptedTake time: 860msTake Memory: 52840KBSubmit time: 2017-02-19 17:49:05****************************************************/新聞熱點
疑難解答
