題意：求離一個城市第k遠(yuǎn)的城市的編號，無負(fù)權(quán)邊。

思路：根據(jù)dijstra算法的特點可以知道，外層循環(huán)n次，每次求出的點就是離源點第i遠(yuǎn)的點的最短路。所以迭代k次，第k次新求出的點即為答案。

1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 using namespace std; 6 7 const int INF = 9999999; 8 const int N = 201; 9 const int M = 20000; 10 int head[N]; 11 int dist[N]; 12 bool visit[N]; 13 int n, m, k, e; 14 15 struct Edge 16 { 17 int v, next, w; 18 } edge[M]; 19 20 void addEdge( int u, int v, int w ) 21 { 22 edge[e].v = v; 23 edge[e].w = w; 24 edge[e].next = head[u]; 25 head[u] = e++; 26 } 27 28 int dij( int s ) 29 { 30 memset( visit, false, sizeof(visit) ); 31 for ( int i = 0; i <= n; i++ ) 32 { 33 dist[i] = INF; 34 } 35 dist[s] = 0; 36 int u; 37 for ( int i = 0; i <= k; i++ ) 38 { 39 u = n; 40 for ( int j = 0; j < n; j++ ) 41 { 42 if ( !visit[j] && dist[j] < dist[u] ) 43 { 44 u = j; 45 } 46 } 47 visit[u] = true; 48 for ( int j = head[u]; j != -1; j = edge[j].next ) 49 { 50 int v = edge[j].v, w = edge[j].w; 51 if ( !visit[v] && dist[u] + w < dist[v] ) 52 { 53 dist[v] = dist[u] + w; 54 } 55 } 56 } 57 return u; 58 } 59 60 int main () 61 { 62 while ( scanf("%d", &n), n ) 63 { 64 scanf("%d", &m); 65 e = 0; 66 memset( head, -1, sizeof(head) ); 67 while ( m-- ) 68 { 69 int u, v, w; 70 scanf("%d%d%d", &u, &v, &w); 71 addEdge( u, v, w ); 72 addEdge( v, u, w ); 73 } 74 scanf("%d", &k); 75 printf("%d\n", dij(0)); 76 } 77 return 0; 78 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/huoxiayu/p/4667553.html

總結(jié)

以上是生活随笔為你收集整理的toj 2870 理解dijstra的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。