pku + 2387

       很郁闷,其实是参考别人的代码才弄明白,我也知道很简单,但是写就。。。看来路还很长很长,不知道怎么用堆! 这题还是用普通的结构!这个算法用的是贪心的算法~~书上思想都有的!
 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 

posted on 2010-06-15 15:11 haozi 阅读(168) 评论(0)  编辑 收藏 引用 所属分类: 图论


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜