对于Dijkstra想做个总结，于是2387来了许多遍
第一次，很久以前的，那个时候还没认真想过Dij，我居然把循环都做完了，而不是找到目标点就跳出。觉得学的时候自己好多东西没认真想。
1
/**//*****************************
2
Source 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