很郁闷,其实是参考别人的代码才弄明白,我也知道很简单,但是写就。。。看来路还很长很长,不知道怎么用堆! 这题还是用普通的结构!这个算法用的是贪心的算法~~书上思想都有的!
1 #include <iostream>
2 #include <algorithm>
3 #include <vector>
4 using namespace std;
5 #define MAX 0x7fffffff
6
7 bool flag[2001];
8 int s1[2001][2001];
9 int dv[2001];
10
11 void di( int t1 )
12 {
13 for(int i = 1;i <= t1;i++) //起点 例如例子 是从 5 返回 1 所以 5为起点
14 dv[i]=s1[t1][i];
15 flag[t1] = true;
16 int wei;
17 for ( int i = 1; i != t1; ++i )
18 {
19 int min = MAX;
20 for ( int j = 1; j <= t1; ++j )
21 {
22 if ( flag[j] != true && dv[j] < min )
23 {
24 wei = j;
25 min = dv[j];
26 }
27 }
28 if( min == MAX )
29 return ; //说明已经没有路了
30 flag[wei] = true;
31 for ( int k = 1; k <= t1; ++k )
32 if( flag[k] != true && s1[wei][k] < MAX && s1[wei][k] + dv[wei] < dv[k] && s1[wei][k] < MAX )
33 dv[k] = s1[wei][k] + dv[wei];
34 }
35 }
36
37 void init( int &t1 )
38 {
39 for ( int i = 1; i != t1+1; ++i )
40 for ( int j = 1; j != t1+1; ++j )
41 if ( i == j )
42 s1[i][j] = 0;
43 else s1[i][j] = MAX;
44 }
45
46 int main()
47 {
48 //freopen( "in.txt","r",stdin );
49 int n,t;
50 cin >> t >> n;
51 init( n );
52 for ( int i = 1; i != t + 1; ++i )
53 {
54 int n1,n2,n3;
55 cin >> n1 >> n2 >> n3;
56 if ( n3 < s1[n1][n2] )
57 {
58 s1[n1][n2] = n3;
59 s1[n2][n1] = n3;
60 }
61 }
62 di( n );
63 cout << dv[1] << endl;
64 return 0;
65 }
66
67