T9的空间

You will never walk alone!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks

对于Dijkstra想做个总结,于是2387来了许多遍
第一次,很久以前的,那个时候还没认真想过Dij,我居然把循环都做完了,而不是找到目标点就跳出。觉得学的时候自己好多东西没认真想。

 1/*****************************
 2Source Code
 3
 4Problem: 2387  User: Torres 
 5Memory: 4164K  Time: 94MS 
 6Language: C++  Result: Accepted 
 7******************************/

 8#include<iostream>
 9using namespace std;
10#define MAX 1005
11const int oo=10000000;
12int dist[MAX][MAX];
13int close[MAX];
14bool used[MAX];
15
16int main()
17{
18    int N,T,i,j;
19    int s,e,len;
20    scanf("%d%d",&T,&N);
21    memset(dist,0x7f,sizeof(dist));
22    memset(used,false,sizeof(used));
23    memset(close,0x7f,sizeof(close));
24    for(i=1;i<=T;i++){
25        scanf("%d%d%d",&s,&e,&len);
26        if(dist[s][e]>len)
27            dist[s][e]=dist[e][s]=len;
28    }

29    for(i=2;i<=N;i++)close[i]=dist[1][i];
30    used[1]=true;
31    for(i=2;i<=N;i++){
32        int min=0;int mlen=oo;
33        for(j=2;j<=N;j++)
34            if(!used[j]&&close[j]<mlen)
35                min=j,mlen=close[j];
36        used[min]=true;
37        for(j=2;j<=N;j++)
38            if(!used[j]&&dist[min][j]<oo){
39                int temp=dist[min][j]+close[min];
40                if(temp<close[j])
41                    close[j]=temp;
42            }

43    }

44    printf("%d\n",close[N]);
45    return 0;
46}

47
48

第二次用链表了内存降下来了
 1Source Code
 2
 3Problem: 2387  User: Torres 
 4Memory: 488K  Time: 110MS 
 5Language: G++  Result: Accepted 
 6
 7Source Code 
 8#include<iostream>
 9#include<algorithm>
10#include<vector>
11using namespace std;
12#define Nmax 1005
13#define oo 0x7fffffff
14
15typedef struct node{
16    int end,len;
17    node(int a=0,int b=oo):end(a),len(b){};
18}
node;
19
20vector<node>dist[Nmax];
21
22int main()
23{
24    int T,N,i,j;
25    int s,e,l;
26    scanf("%d%d",&T,&N);
27    for(i=1;i<=T;i++){
28        scanf("%d%d%d",&s,&e,&l);
29        dist[s].push_back(node(e,l));
30        dist[e].push_back(node(s,l));
31    }

32    vector<bool>used(N+1,false);
33    vector<int>closed(N+1,oo);
34    used[1]=true;
35    int len=dist[1].size();
36    for(i=0;i<len;i++
37        if(closed[dist[1][i].end]>dist[1][i].len)
38            closed[dist[1][i].end]=dist[1][i].len;
39    for(i=1;i<N;i++){
40        int min=0,minlen=oo;
41        for(j=2;j<=N;j++)
42            if(!used[j]&&closed[j]<minlen){
43                min=j;
44                minlen=closed[j];
45            }

46        used[min]=true;
47        for(j=0;j<dist[min].size();j++)
48            if(!used[dist[min][j].end]&&minlen+dist[min][j].len<closed[dist[min][j].end])
49                closed[dist[min][j].end]=minlen+dist[min][j].len;
50    }

51    printf("%d\n",closed[N]);
52    return 0;
53}

54
55

第三次用了priority_queue
 1Source Code
 2
 3Problem: 2387  User: Torres 
 4Memory: 496K  Time: 63MS 
 5Language: G++  Result: Accepted 
 6
 7Source Code 
 8#include<iostream>
 9#include<vector>
10#include<algorithm>
11#include<queue>
12using namespace std;
13
14const int Nmax=1005;
15const int oo=0x7fffffff;
16
17typedef struct node{
18    int end,len;
19    node(int a=0,int b=oo):end(a),len(b){};
20    bool operator<(const node &a)const{
21        return this->len>a.len;
22    }

23}
node;
24
25vector<node>dist[Nmax];
26
27int main()
28{
29    int N,M,i,j;
30    int s,e,l;
31    scanf("%d%d",&M,&N);
32    for(i=1;i<=M;i++){
33        scanf("%d%d%d",&s,&e,&l);
34        dist[s].push_back(node(e,l));
35        dist[e].push_back(node(s,l));
36    }

37
38    vector<int>closed(N+1,oo);
39    vector<bool>used(N+1,false);
40    priority_queue<node>minclosed;
41    int sz=dist[1].size();
42    
43    for(i=0;i<sz;i++){
44        closed[dist[1][i].end]=dist[1][i].len;
45        minclosed.push(dist[1][i]);
46    }

47    used[1]=true;
48
49    for(i=1;i<N;i++){
50        while(used[minclosed.top().end])
51            minclosed.pop();
52        node ntemp=minclosed.top();
53        if(ntemp.end==N||ntemp.len==oo){closed[N]=ntemp.len;break;}
54        minclosed.pop();
55        used[ntemp.end]=true;
56
57        sz=dist[ntemp.end].size();
58
59        for(j=0;j<sz;j++){
60            int en=dist[ntemp.end][j].end;
61            int le=ntemp.len+dist[ntemp.end][j].len;
62            if(!used[en]&&le<closed[en]){
63                closed[en]=le;
64                minclosed.push(node(en,le));
65            }

66        }

67        
68    }

69    printf("%d\n",closed[N]);
70    return 0;
71}

72
73

第四次用了heap
 1Source Code
 2
 3Problem: 2387  User: Torres 
 4Memory: 496K  Time: 63MS 
 5Language: G++  Result: Accepted 
 6
 7Source Code 
 8#include<iostream>
 9#include<vector>
10#include<algorithm>
11using namespace std;
12
13const int Nmax=1005;
14const int oo=0x7fffffff;
15
16typedef struct node{
17    int end,len;
18    node(int a,int b):end(a),len(b){};
19    bool operator<(const node &a)const{
20        return this->len>a.len;
21    }

22}
node;
23
24vector<node>dist[Nmax];
25
26int main()
27{
28    int N,M,i,j;
29    int s,e,l;
30    scanf("%d%d",&M,&N);
31    for(i=1;i<=M;i++){
32        scanf("%d%d%d",&s,&e,&l);
33        dist[s].push_back(node(e,l));dist[e].push_back(node(s,l));
34    }

35
36    vector<int>closed(N+1,oo);
37    vector<bool>used(N+1,false);
38    vector<node>minclosed;
39    int sz=dist[1].size();
40    
41    for(i=0;i<sz;i++){
42        closed[dist[1][i].end]=dist[1][i].len;
43        minclosed.push_back(dist[1][i]);
44    }

45    used[1]=true;
46    make_heap(minclosed.begin(),minclosed.end());
47
48    for(i=1;i<N;i++){
49        while(used[minclosed.front().end]){
50            pop_heap(minclosed.begin(),minclosed.end());
51            minclosed.pop_back();
52        }

53        pop_heap(minclosed.begin(),minclosed.end());
54        node ntemp=minclosed.back();
55        if(ntemp.end==N||ntemp.len==oo){closed[N]=ntemp.len;break;}
56        minclosed.pop_back();
57        used[ntemp.end]=true;
58
59        sz=dist[ntemp.end].size();
60
61        for(j=0;j<sz;j++){
62            int en=dist[ntemp.end][j].end;
63            int le=ntemp.len+dist[ntemp.end][j].len;
64            if(!used[en]&&le<closed[en]){
65                closed[en]=le;
66                minclosed.push_back(node(en,le));
67                push_heap(minclosed.begin(),minclosed.end());
68            }

69        }

70    }

71    printf("%d\n",closed[N]);
72    return 0;
73}

74
75
posted on 2008-09-02 19:05 Torres 阅读(1110) 评论(0)  编辑 收藏 引用 所属分类: Graph

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理