单源最短路

dij priority queue

  1 #include<cstdio>
  2 #include<queue>
  3 using namespace std;
  4 typedef __int64 LL;
  5 const LL inf=0x3f3f3f3f3f3f3f3fLL;
  6 class Dijkstra { ///单源最短路 o(ME*log(MV))
  7     typedef LL typec;///边权的类型
  8     static const int ME=1e5+10;///边的个数
  9     static const int MV=5e4+10;///点的个数
 10     struct Q {
 11         int id;
 12         typec w;
 13         friend bool operator <(const Q &a,const Q &b) {
 14             return a.w>b.w;
 15         }
 16     } now;
 17     priority_queue<Q> q;
 18     struct E {
 19         int v,next;
 20         typec w;
 21     } e[ME];
 22     int n,le,head[MV],u,v,i;
 23     typec dist[MV],w;
 24     bool used[MV];
 25 public:
 26     void init(int tn) {///传入点的个数
 27         n=tn;
 28         le=0;
 29         for(i=0; i<=n; i++) head[i]=-1;
 30     }
 31     void add(int u,int v,typec w) {
 32         e[le].v=v;
 33         e[le].w=w;
 34         e[le].next=head[u];
 35         head[u]=le++;
 36     }
 37     void solve(int s) {///传入起点
 38         for(i=0; i<=n; i++) {
 39             used[i]=true;
 40             dist[i]=inf;
 41         }
 42         dist[s]=0;
 43         now.id=s;
 44         now.w=0;
 45         while(!q.empty()) q.pop();
 46         q.push(now);
 47         while(!q.empty()) {
 48             now=q.top();
 49             q.pop();
 50             u=now.id;
 51             if(used[u]) {
 52                 used[u]=false;
 53                 for(i=head[u]; ~i; i=e[i].next) {
 54                     v=e[i].v;
 55                     w=e[i].w;
 56                     if(used[v]&&dist[v]>w+dist[u]) {
 57                         dist[v]=w+dist[u];
 58                         now.id=v;
 59                         now.w=dist[v];
 60                         q.push(now);
 61                     }
 62                 }
 63             }
 64         }
 65     }
 66     typec getdist(int id) {
 67         return dist[id];
 68     }
 69 } g;
 70 int val[50010];
 71 int main(){
 72     int t,n,m,u,v,w;
 73     while(~scanf("%d",&t)){
 74         while(t--){
 75             scanf("%d%d",&n,&m);
 76             for(int i=1;i<=n;i++){
 77                 scanf("%d",&val[i]);
 78             }
 79             g.init(n);
 80             while(m--){
 81                 scanf("%d%d%d",&u,&v,&w);
 82                 g.add(u,v,w);
 83                 g.add(v,u,w);
 84             }
 85             g.solve(1);
 86             bool flag=true;
 87             LL sum=0;
 88             for(int i=1;i<=n;i++){
 89                 if(g.getdist(i)==inf){
 90                     flag=false;
 91                     break;
 92                 }
 93                 sum+=g.getdist(i)*val[i];
 94             }
 95             if(!flag){
 96                 puts("No Answer");
 97             }
 98             else{
 99                 printf("%I64d
",sum);
100             }
101         }
102     }
103     return 0;
104 }

View Code

spfa

 1 #include<cstdio>
 2 #include<queue>
 3 using namespace std;
 4 typedef __int64 LL;
 5 const LL inf=0x3f3f3f3f3f3f3f3fLL;
 6 class Spfa { ///单源最短路o(k*ME)k~=2
 7     typedef LL typec;///边权的类型
 8     static const int ME=1e5+10;///边的个数
 9     static const int MV=5e4+10;///点的个数
10     struct E {
11         int v,next;
12         typec w;
13     } e[ME];
14     int n,le,head[MV],inque[MV],i,u,v;
15     typec dist[MV];
16     bool used[MV];
17     queue<int> q;
18 public:
19     void init(int tn) { ///传入点的个数
20         n=tn;
21         le=0;
22         for(i=0; i<=n; i++) head[i]=-1;
23     }
24     void add(int u,int v,typec w) {
25         e[le].v=v;
26         e[le].w=w;
27         e[le].next=head[u];
28         head[u]=le++;
29     }
30     bool solve(int s) { ///传入起点,存在负环返回false
31         for(i=0; i<=n; i++) {
32             dist[i]=inf;
33             used[i]=true;
34             inque[i]=0;
35         }
36         used[s]=false;
37         dist[s]=0;
38         inque[s]++;
39         while(!q.empty()) q.pop();
40         q.push(s);
41         while(!q.empty()) {
42             u=q.front();
43             q.pop();
44             used[u]=true;
45             for(i=head[u]; ~i; i=e[i].next) {
46                 v=e[i].v;
47                 if(dist[v]>dist[u]+e[i].w) {
48                     dist[v]=dist[u]+e[i].w;
49                     if(used[v]) {
50                         used[v]=false;
51                         q.push(v);
52                         inque[v]++;
53                         if(inque[v]>n) return false;
54                     }
55                 }
56             }
57         }
58         return true;
59     }
60     typec getdist(int id) {
61         return dist[id];
62     }
63 } g;
64 
65 int val[50010];
66 int main(){
67     int t,n,m,u,v,w;
68     while(~scanf("%d",&t)){
69         while(t--){
70             scanf("%d%d",&n,&m);
71             for(int i=1;i<=n;i++){
72                 scanf("%d",&val[i]);
73             }
74             g.init(n);
75             while(m--){
76                 scanf("%d%d%d",&u,&v,&w);
77                 g.add(u,v,w);
78                 g.add(v,u,w);
79             }
80             g.solve(1);
81             bool flag=true;
82             LL sum=0;
83             for(int i=1;i<=n;i++){
84                 if(g.getdist(i)==inf){
85                     flag=false;
86                     break;
87                 }
88                 sum+=g.getdist(i)*val[i];
89             }
90             if(!flag){
91                 puts("No Answer");
92             }
93             else{
94                 printf("%I64d
",sum);
95             }
96         }
97     }
98     return 0;
99 }

View Code

Invitation Cards http://poj.org/problem?id=1511

dij+priority queue o （elogv）

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #define mt(a,b) memset(a,b,sizeof(a))
  5 using namespace std;
  6 typedef long long LL;
  7 const int inf=0x3f3f3f3f;
  8 class Dijkstra { ///单源最短路 o(ME*log(MV))
  9     typedef int typec;///边权的类型
 10     static const int ME=1e6+10;///边的个数
 11     static const int MV=1e6+10;///点的个数
 12     struct Q {
 13         int id;
 14         typec w;
 15         friend bool operator <(const Q &a,const Q &b) {
 16             return a.w>b.w;
 17         }
 18     } now;
 19     priority_queue<Q> q;
 20     struct E {
 21         int v,next;
 22         typec w;
 23     } e[ME];
 24     int n,le,head[MV];
 25     typec dist[MV];
 26     bool used[MV];
 27 public:
 28     void init(int tn) {///传入点的个数
 29         n=tn;
 30         le=0;
 31         mt(head,-1);
 32     }
 33     void add(int u,int v,typec w) {
 34         e[le].v=v;
 35         e[le].w=w;
 36         e[le].next=head[u];
 37         head[u]=le++;
 38     }
 39     void solve(int s) {///传入起点
 40         for(int i=0; i<=n; i++) {
 41             used[i]=true;
 42             dist[i]=inf;
 43         }
 44         dist[s]=0;
 45         now.id=s;
 46         now.w=0;
 47         while(!q.empty()) q.pop();
 48         q.push(now);
 49         while(!q.empty()) {
 50             now=q.top();
 51             q.pop();
 52             int u=now.id;
 53             if(used[u]) {
 54                 used[u]=false;
 55                 for(int i=head[u]; ~i; i=e[i].next) {
 56                     int v=e[i].v;
 57                     typec w=e[i].w;
 58                     if(used[v]&&dist[v]>w+dist[u]) {
 59                         dist[v]=w+dist[u];
 60                         now.id=v;
 61                         now.w=dist[v];
 62                         q.push(now);
 63                     }
 64                 }
 65             }
 66         }
 67     }
 68     typec getdist(int id) {
 69         return dist[id];
 70     }
 71 } gx;
 72 struct IN{
 73     int u,v,w;
 74 }e[1000010];
 75 int main() {
 76     int t,n,m,u,v,w;
 77     while(~scanf("%d",&t)) {
 78         while(t--) {
 79             scanf("%d%d",&n,&m);
 80             gx.init(n);
 81             for(int i=0;i<m;i++) {
 82                 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
 83                 gx.add(e[i].u,e[i].v,e[i].w);
 84             }
 85             gx.solve(1);
 86             LL ans=0;
 87             for(int i=1; i<=n; i++) {
 88                 ans+=gx.getdist(i);
 89             }
 90             gx.init(n);
 91             for(int i=0;i<m;i++){
 92                 gx.add(e[i].v,e[i].u,e[i].w);
 93             }
 94             gx.solve(1);
 95             for(int i=1; i<=n; i++) {
 96                 ans+=gx.getdist(i);
 97             }
 98             printf("%lld
",ans);
 99         }
100     }
101     return 0;
102 }

View Code

spfa o(2e)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 typedef __int64 LL;
 7 const int inf=0x3f3f3f3f;
 8 const int M=1000010;
 9 class Spfa { ///单源最短路o(k*ME)k~=2
10     typedef int typec;///边权的类型
11     static const int ME=1e6+10;///边的个数
12     static const int MV=1e6+10;///点的个数
13     struct E {
14         int v,next;
15         typec w;
16     } e[ME];
17     int n,le,head[MV],inque[MV],i,u,v;
18     typec dist[MV];
19     bool used[MV];
20     queue<int> q;
21 public:
22     void init(int tn) { ///传入点的个数
23         n=tn;
24         le=0;
25         for(i=0;i<=n;i++) head[i]=-1;
26     }
27     void add(int u,int v,typec w) {
28         e[le].v=v;
29         e[le].w=w;
30         e[le].next=head[u];
31         head[u]=le++;
32     }
33     bool solve(int s) { ///传入起点,存在负环返回false
34         for(i=0; i<=n; i++) {
35             dist[i]=inf;
36             used[i]=true;
37             inque[i]=0;
38         }
39         used[s]=false;
40         dist[s]=0;
41         inque[s]++;
42         while(!q.empty()) q.pop();
43         q.push(s);
44         while(!q.empty()) {
45             u=q.front();
46             q.pop();
47             used[u]=true;
48             for(i=head[u]; ~i; i=e[i].next) {
49                 v=e[i].v;
50                 if(dist[v]>dist[u]+e[i].w) {
51                     dist[v]=dist[u]+e[i].w;
52                     if(used[v]) {
53                         used[v]=false;
54                         q.push(v);
55                         inque[v]++;
56                         if(inque[v]>n) return false;
57                     }
58                 }
59             }
60         }
61         return true;
62     }
63     typec getdist(int id) {
64         return dist[id];
65     }
66 } gx;
67 struct IN {
68     int u,v,w;
69 } e[M];
70 int main() {
71     int t,n,m,u,v,w;
72     while(~scanf("%d",&t)) {
73         while(t--) {
74             scanf("%d%d",&n,&m);
75             gx.init(n);
76             for(int i=0; i<m; i++) {
77                 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
78                 gx.add(e[i].u,e[i].v,e[i].w);
79             }
80             gx.solve(1);
81             LL ans=0;
82             for(int i=1; i<=n; i++) {
83                 ans+=gx.getdist(i);
84             }
85             gx.init(n);
86             for(int i=0; i<m; i++) {
87                 gx.add(e[i].v,e[i].u,e[i].w);
88             }
89             gx.solve(1);
90             for(int i=1; i<=n; i++) {
91                 ans+=gx.getdist(i);
92             }
93             printf("%I64d
",ans);
94         }
95     }
96     return 0;
97 }

View Code

MPI Maelstrom http://poj.org/problem?id=1502

dij+priority queue o （elogv）

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<stack>
  5 #include<algorithm>
  6 #define mt(a,b) memset(a,b,sizeof(a))
  7 using namespace std;
  8 typedef __int64 LL;
  9 const int inf=0x3f3f3f3f;
 10 class Dijkstra { ///单源最短路 o(ME*log(MV))
 11     typedef int typec;///边权的类型
 12     static const int ME=1e4+10;///边的个数
 13     static const int MV=1e2+10;///点的个数
 14     struct Q {
 15         int id;
 16         typec w;
 17         friend bool operator <(const Q &a,const Q &b) {
 18             return a.w>b.w;
 19         }
 20     } now;
 21     priority_queue<Q> q;
 22     struct E {
 23         int v,next;
 24         typec w;
 25     } e[ME];
 26     int n,le,head[MV],u,v,i;
 27     typec dist[MV],w;
 28     bool used[MV];
 29 public:
 30     void init(int tn) {///传入点的个数
 31         n=tn;
 32         le=0;
 33         mt(head,-1);
 34     }
 35     void add(int u,int v,typec w) {
 36         e[le].v=v;
 37         e[le].w=w;
 38         e[le].next=head[u];
 39         head[u]=le++;
 40     }
 41     void solve(int s) {///传入起点
 42         for(i=0; i<=n; i++) {
 43             used[i]=true;
 44             dist[i]=inf;
 45         }
 46         dist[s]=0;
 47         now.id=s;
 48         now.w=0;
 49         while(!q.empty()) q.pop();
 50         q.push(now);
 51         while(!q.empty()) {
 52             now=q.top();
 53             q.pop();
 54             u=now.id;
 55             if(used[u]) {
 56                 used[u]=false;
 57                 for(i=head[u]; ~i; i=e[i].next) {
 58                     v=e[i].v;
 59                     w=e[i].w;
 60                     if(used[v]&&dist[v]>w+dist[u]) {
 61                         dist[v]=w+dist[u];
 62                         now.id=v;
 63                         now.w=dist[v];
 64                         q.push(now);
 65                     }
 66                 }
 67             }
 68         }
 69     }
 70     typec getdist(int id) {
 71         return dist[id];
 72     }
 73 } gx;
 74 int main(){
 75     int n;
 76     char tmp[32];
 77     while(~scanf("%d",&n)){
 78         gx.init(n);
 79         for(int i=2;i<=n;i++){
 80             for(int j=1;j<i;j++){
 81                 scanf("%s",tmp);
 82                 if(tmp[0]=='x'){
 83                     continue;
 84                 }
 85                 int sum=0;
 86                 for(int k=0;tmp[k];k++){
 87                     sum*=10;
 88                     sum+=tmp[k]-'0';
 89                 }
 90                 gx.add(i,j,sum);
 91                 gx.add(j,i,sum);
 92             }
 93         }
 94         gx.solve(1);
 95         int ans=0;
 96         for(int i=1;i<=n;i++){
 97             ans=max(ans,gx.getdist(i));
 98         }
 99         printf("%d
",ans);
100     }
101     return 0;
102 }

View Code

dij n^2

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int inf=0x3f3f3f3f;
 5 class Dijkstra_Matrix { ///单源最短路 (邻接阵)o(MV^2)
 6     typedef int typec;///边权的类型
 7     static const int MV=1e2+10;///点的个数
 8     int n,pre[MV],i,j,k;
 9     typec mat[MV][MV],dist[MV];
10     bool vis[MV];
11 public:
12     void init(int tn) { ///传入点的个数
13         n=tn;
14         for(i=0; i<=n; i++)
15             for(j=0; j<=n; j++)
16                 mat[i][j]=i==j?0:inf;
17     }
18     void add(int u,int v,typec w) {
19         mat[u][v]=min(mat[u][v],w);
20     }
21     void solve(int s) { ///传入起点
22         for(i=0; i<=n; i++) {
23             dist[i]=inf;
24             vis[i]=false;
25             pre[i]=-1;
26         }
27         for(dist[s]=0,j=0; j<=n; j++) {
28             for(k=-1,i=0; i<=n; i++) {
29                 if(!vis[i]&&(k==-1||dist[i]<dist[k])) {
30                     k=i;
31                 }
32             }
33             for(vis[k]=true,i=0; i<=n; i++) {
34                 if(!vis[i]&&dist[k]+mat[k][i]<dist[i]) {
35                     dist[i]=dist[k]+mat[pre[i]=k][i];
36                 }
37             }
38         }
39     }
40     typec getdist(int id) {
41         return dist[id];
42     }
43 } gx;
44 int main() {
45     int n;
46     char tmp[32];
47     while(~scanf("%d",&n)) {
48         gx.init(n);
49         for(int i=2; i<=n; i++) {
50             for(int j=1; j<i; j++) {
51                 scanf("%s",tmp);
52                 if(tmp[0]=='x') {
53                     continue;
54                 }
55                 int sum=0;
56                 for(int k=0; tmp[k]; k++) {
57                     sum*=10;
58                     sum+=tmp[k]-'0';
59                 }
60                 gx.add(i,j,sum);
61                 gx.add(j,i,sum);
62             }
63         }
64         gx.solve(1);
65         int ans=0;
66         for(int i=1; i<=n; i++) {
67             ans=max(ans,gx.getdist(i));
68         }
69         printf("%d
",ans);
70     }
71     return 0;
72 }

View Code

spfa o(2e)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<queue>
 5 #define mt(a,b) memset(a,b,sizeof(a))
 6 using namespace std;
 7 const int inf=0x3f3f3f3f;
 8 class Spfa { ///单源最短路o(2*ME)
 9     typedef int typec;///边权的类型
10     static const int ME=1000010;///边的个数
11     static const int MV=1000010;///点的个数
12     struct E {
13         int v,next;
14         typec w;
15     } e[ME];
16     int n,le,head[MV],inque[MV];
17     typec dist[MV];
18     bool used[MV];
19     queue<int> q;
20 public:
21     void init(int tn) { ///传入点的个数
22         n=tn;
23         le=0;
24         mt(head,-1);
25     }
26     void add(int u,int v,typec w) {
27         e[le].v=v;
28         e[le].w=w;
29         e[le].next=head[u];
30         head[u]=le++;
31     }
32     bool solve(int s) { ///传入起点，下标0开始,存在负环返回false
33         for(int i=0; i<n; i++) {
34             dist[i]=inf;
35             used[i]=true;
36             inque[i]=0;
37         }
38         used[s]=false;
39         dist[s]=0;
40         inque[s]++;
41         while(!q.empty()) q.pop();
42         q.push(s);
43         while(!q.empty()) {
44             int u=q.front();
45             q.pop();
46             used[u]=true;
47             for(int i=head[u]; ~i; i=e[i].next) {
48                 int v=e[i].v;
49                 if(dist[v]>dist[u]+e[i].w) {
50                     dist[v]=dist[u]+e[i].w;
51                     if(used[v]) {
52                         used[v]=false;
53                         q.push(v);
54                         inque[v]++;
55                         if(inque[v]>n) return false;
56                     }
57                 }
58             }
59         }
60         return true;
61     }
62     typec getdist(int id) {
63         return dist[id];
64     }
65 } gx;
66 int main() {
67     int n;
68     char tmp[32];
69     while(~scanf("%d",&n)) {
70         gx.init(n);
71         for(int i=2; i<=n; i++) {
72             for(int j=1; j<i; j++) {
73                 scanf("%s",tmp);
74                 if(tmp[0]=='x') {
75                     continue;
76                 }
77                 int sum=0;
78                 for(int k=0; tmp[k]; k++) {
79                     sum*=10;
80                     sum+=tmp[k]-'0';
81                 }
82                 gx.add(i-1,j-1,sum);
83                 gx.add(j-1,i-1,sum);
84             }
85         }
86         gx.solve(0);
87         int ans=0;
88         for(int i=0; i<n; i++) {
89             ans=max(ans,gx.getdist(i));
90         }
91         printf("%d
",ans);
92     }
93     return 0;
94 }

View Code

bell ford ve

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<queue>
  5 #define mt(a,b) memset(a,b,sizeof(a))
  6 using namespace std;
  7 const int inf=0x3f3f3f3f;
  8 class Bellman_ford { ///单源最短路o(MV*ME)
  9     typedef int typec;///边权的类型
 10     static const int ME=1000010;///边的个数
 11     static const int MV=1000010;///点的个数
 12     struct E {
 13         int u,v,next;
 14         typec w;
 15     } e[ME];
 16     int n,le,head[MV];
 17     bool used[MV];
 18     typec dist[MV];
 19 public:
 20     void init(int tn) { ///传入点的个数
 21         n=tn;
 22         le=0;
 23         mt(head,-1);
 24     }
 25     void add(int u,int v,typec w) {
 26         e[le].u=u;
 27         e[le].v=v;
 28         e[le].w=w;
 29         e[le].next=head[u];
 30         head[u]=le++;
 31     }
 32     bool solve(int s) {  ///传入起点，下标0开始，为真最短路成功,为假存在负环
 33         for(int i=0; i<n; i++) {
 34             used[i]=true;
 35             dist[i]=inf;
 36         }
 37         used[s]=false;
 38         dist[s]=0;
 39         for(int i=head[s]; ~i; i=e[i].next){
 40             int v=e[i].v;
 41             dist[v]=min(dist[v],e[i].w);
 42         }
 43         for(int i=1; i<n; i++) {
 44             typec sma=inf;
 45             int p;
 46             for(int j=0; j<n; j++) {
 47                 if(used[j]&&sma>dist[j]) {
 48                     p=j;
 49                     sma=dist[j];
 50                 }
 51             }
 52             used[p]=false;
 53             for(int j=head[p]; ~j; j=e[j].next) {
 54                 int v=e[j].v;
 55                 if(!used[v]) continue;
 56                 dist[v]=min(dist[v],e[j].w+dist[e[j].u]);
 57             }
 58         }
 59         bool flag=true;
 60         int j;
 61         for(j=0; flag&&j<=n; j++) {
 62             flag=false;
 63             for(int i=0; i<n; i++) {
 64                 for(int k=head[i]; ~k; k=e[k].next) {
 65                     if(dist[e[k].v]>e[k].w+dist[i]) {
 66                         dist[e[k].v]=e[k].w+dist[i];
 67                         flag=true;
 68                     }
 69                 }
 70             }
 71         }
 72         return j<=n;
 73     }
 74     typec getdist(int id){
 75         return dist[id];
 76     }
 77 }gx;
 78 int main() {
 79     int n;
 80     char tmp[32];
 81     while(~scanf("%d",&n)) {
 82         gx.init(n);
 83         for(int i=2; i<=n; i++) {
 84             for(int j=1; j<i; j++) {
 85                 scanf("%s",tmp);
 86                 if(tmp[0]=='x') {
 87                     continue;
 88                 }
 89                 int sum=0;
 90                 for(int k=0; tmp[k]; k++) {
 91                     sum*=10;
 92                     sum+=tmp[k]-'0';
 93                 }
 94                 gx.add(i-1,j-1,sum);
 95                 gx.add(j-1,i-1,sum);
 96             }
 97         }
 98         gx.solve(0);
 99         int ans=0;
100         for(int i=0; i<n; i++) {
101             ans=max(ans,gx.getdist(i));
102         }
103         printf("%d
",ans);
104     }
105     return 0;
106 }

View Code

Tram http://poj.org/problem?id=1847

dij+priority queue o （elogv）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<stack>
 5 #include<algorithm>
 6 #define mt(a,b) memset(a,b,sizeof(a))
 7 using namespace std;
 8 typedef __int64 LL;
 9 const int inf=0x3f3f3f3f;
10 class Dijkstra { ///单源最短路 o(ME*log(MV))
11     typedef int typec;///边权的类型
12     static const int ME=1e4+10;///边的个数
13     static const int MV=1e2+10;///点的个数
14     struct Q {
15         int id;
16         typec w;
17         friend bool operator <(const Q &a,const Q &b) {
18             return a.w>b.w;
19         }
20     } now;
21     priority_queue<Q> q;
22     struct E {
23         int v,next;
24         typec w;
25     } e[ME];
26     int n,le,head[MV],u,v,i;
27     typec dist[MV],w;
28     bool used[MV];
29 public:
30     void init(int tn) {///传入点的个数
31         n=tn;
32         le=0;
33         for(i=0;i<=n;i++) head[i]=-1;
34     }
35     void add(int u,int v,typec w) {
36         e[le].v=v;
37         e[le].w=w;
38         e[le].next=head[u];
39         head[u]=le++;
40     }
41     void solve(int s) {///传入起点
42         for(i=0; i<=n; i++) {
43             used[i]=true;
44             dist[i]=inf;
45         }
46         dist[s]=0;
47         now.id=s;
48         now.w=0;
49         while(!q.empty()) q.pop();
50         q.push(now);
51         while(!q.empty()) {
52             now=q.top();
53             q.pop();
54             u=now.id;
55             if(used[u]) {
56                 used[u]=false;
57                 for(i=head[u]; ~i; i=e[i].next) {
58                     v=e[i].v;
59                     w=e[i].w;
60                     if(used[v]&&dist[v]>w+dist[u]) {
61                         dist[v]=w+dist[u];
62                         now.id=v;
63                         now.w=dist[v];
64                         q.push(now);
65                     }
66                 }
67             }
68         }
69     }
70     typec getdist(int id) {
71         return dist[id];
72     }
73 } gx;
74 int main(){
75     int n,a,b;
76     while(~scanf("%d%d%d",&n,&a,&b)){
77         gx.init(n);
78         for(int i=1;i<=n;i++){
79             int m,to;
80             scanf("%d",&m);
81             for(int j=0;j<m;j++){
82                 scanf("%d",&to);
83                 if(j!=0)    gx.add(i,to,1);
84                 else        gx.add(i,to,0);
85             }
86         }
87         gx.solve(a);
88         int ans=gx.getdist(b);
89         if(ans>1024) ans=-1;
90         printf("%d
",ans);
91     }
92     return 0;
93 }

View Code

dij n^2

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<stack>
 5 #include<algorithm>
 6 #define mt(a,b) memset(a,b,sizeof(a))
 7 using namespace std;
 8 typedef __int64 LL;
 9 const int inf=0x3f3f3f3f;
10 class Dijkstra_Matrix { ///单源最短路 (邻接阵)o(MV^2)
11     typedef int typec;///边权的类型
12     static const int MV=1e2+10;///点的个数
13     int n,pre[MV],i,j,k;
14     typec mat[MV][MV],dist[MV];
15     bool vis[MV];
16 public:
17     void init(int tn) { ///传入点的个数
18         n=tn;
19         for(i=0; i<=n; i++)
20             for(j=0; j<=n; j++)
21                 mat[i][j]=i==j?0:inf;
22     }
23     void add(int u,int v,typec w) {
24         mat[u][v]=min(mat[u][v],w);
25     }
26     void solve(int s) { ///传入起点
27         for(i=0; i<=n; i++) {
28             dist[i]=inf;
29             vis[i]=false;
30             pre[i]=-1;
31         }
32         for(dist[s]=0,j=0; j<=n; j++) {
33             for(k=-1,i=0; i<=n; i++) {
34                 if(!vis[i]&&(k==-1||dist[i]<dist[k])) {
35                     k=i;
36                 }
37             }
38             for(vis[k]=true,i=0; i<=n; i++) {
39                 if(!vis[i]&&dist[k]+mat[k][i]<dist[i]) {
40                     dist[i]=dist[k]+mat[pre[i]=k][i];
41                 }
42             }
43         }
44     }
45     typec getdist(int id) {
46         return dist[id];
47     }
48 } gx;
49 int main(){
50     int n,a,b;
51     while(~scanf("%d%d%d",&n,&a,&b)){
52         gx.init(n);
53         for(int i=1;i<=n;i++){
54             int m,to;
55             scanf("%d",&m);
56             for(int j=0;j<m;j++){
57                 scanf("%d",&to);
58                 if(j!=0)    gx.add(i,to,1);
59                 else        gx.add(i,to,0);
60             }
61         }
62         gx.solve(a);
63         int ans=gx.getdist(b);
64         if(ans>1024) ans=-1;
65         printf("%d
",ans);
66     }
67     return 0;
68 }

View Code

spfa o(2e)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<stack>
 5 #include<algorithm>
 6 #define mt(a,b) memset(a,b,sizeof(a))
 7 using namespace std;
 8 typedef __int64 LL;
 9 const int inf=0x3f3f3f3f;
10 class Spfa { ///单源最短路o(2*ME)
11     typedef int typec;///边权的类型
12     static const int ME=1000010;///边的个数
13     static const int MV=1000010;///点的个数
14     struct E {
15         int v,next;
16         typec w;
17     } e[ME];
18     int n,le,head[MV],inque[MV];
19     typec dist[MV];
20     bool used[MV];
21     queue<int> q;
22 public:
23     void init(int tn) { ///传入点的个数
24         n=tn;
25         le=0;
26         mt(head,-1);
27     }
28     void add(int u,int v,typec w) {
29         e[le].v=v;
30         e[le].w=w;
31         e[le].next=head[u];
32         head[u]=le++;
33     }
34     bool solve(int s) { ///传入起点，下标0开始,存在负环返回false
35         for(int i=0; i<n; i++) {
36             dist[i]=inf;
37             used[i]=true;
38             inque[i]=0;
39         }
40         used[s]=false;
41         dist[s]=0;
42         inque[s]++;
43         while(!q.empty()) q.pop();
44         q.push(s);
45         while(!q.empty()) {
46             int u=q.front();
47             q.pop();
48             used[u]=true;
49             for(int i=head[u]; ~i; i=e[i].next) {
50                 int v=e[i].v;
51                 if(dist[v]>dist[u]+e[i].w) {
52                     dist[v]=dist[u]+e[i].w;
53                     if(used[v]) {
54                         used[v]=false;
55                         q.push(v);
56                         inque[v]++;
57                         if(inque[v]>n) return false;
58                     }
59                 }
60             }
61         }
62         return true;
63     }
64     typec getdist(int id) {
65         return dist[id];
66     }
67 } gx;
68 int main(){
69     int n,a,b;
70     while(~scanf("%d%d%d",&n,&a,&b)){
71         gx.init(n);
72         for(int i=1;i<=n;i++){
73             int m,to;
74             scanf("%d",&m);
75             for(int j=0;j<m;j++){
76                 scanf("%d",&to);
77                 if(j!=0)    gx.add(i-1,to-1,1);
78                 else        gx.add(i-1,to-1,0);
79             }
80         }
81         gx.solve(a-1);
82         int ans=gx.getdist(b-1);
83         if(ans>1024) ans=-1;
84         printf("%d
",ans);
85     }
86     return 0;
87 }

View Code

bell ford ve

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<stack>
 5 #include<algorithm>
 6 #define mt(a,b) memset(a,b,sizeof(a))
 7 using namespace std;
 8 typedef __int64 LL;
 9 const int inf=0x3f3f3f3f;
10 class Bellman_ford { ///单源最短路o(MV*ME)
11     typedef int typec;///边权的类型
12     static const int ME=1000010;///边的个数
13     static const int MV=1000010;///点的个数
14     struct E {
15         int u,v,next;
16         typec w;
17     } e[ME];
18     int n,le,head[MV];
19     bool used[MV];
20     typec dist[MV];
21 public:
22     void init(int tn) { ///传入点的个数
23         n=tn;
24         le=0;
25         mt(head,-1);
26     }
27     void add(int u,int v,typec w) {
28         e[le].u=u;
29         e[le].v=v;
30         e[le].w=w;
31         e[le].next=head[u];
32         head[u]=le++;
33     }
34     bool solve(int s) {  ///传入起点，下标0开始，为真最短路成功,为假存在负环
35         for(int i=0; i<n; i++) {
36             used[i]=true;
37             dist[i]=inf;
38         }
39         used[s]=false;
40         dist[s]=0;
41         for(int i=head[s]; ~i; i=e[i].next){
42             int v=e[i].v;
43             dist[v]=min(dist[v],e[i].w);
44         }
45         for(int i=1; i<n; i++) {
46             typec sma=inf;
47             int p;
48             for(int j=0; j<n; j++) {
49                 if(used[j]&&sma>dist[j]) {
50                     p=j;
51                     sma=dist[j];
52                 }
53             }
54             used[p]=false;
55             for(int j=head[p]; ~j; j=e[j].next) {
56                 int v=e[j].v;
57                 if(!used[v]) continue;
58                 dist[v]=min(dist[v],e[j].w+dist[e[j].u]);
59             }
60         }
61         bool flag=true;
62         int j;
63         for(j=0; flag&&j<=n; j++) {
64             flag=false;
65             for(int i=0; i<n; i++) {
66                 for(int k=head[i]; ~k; k=e[k].next) {
67                     if(dist[e[k].v]>e[k].w+dist[i]) {
68                         dist[e[k].v]=e[k].w+dist[i];
69                         flag=true;
70                     }
71                 }
72             }
73         }
74         return j<=n;
75     }
76     typec getdist(int id){
77         return dist[id];
78     }
79 }gx;
80 int main(){
81     int n,a,b;
82     while(~scanf("%d%d%d",&n,&a,&b)){
83         gx.init(n);
84         for(int i=1;i<=n;i++){
85             int m,to;
86             scanf("%d",&m);
87             for(int j=0;j<m;j++){
88                 scanf("%d",&to);
89                 if(j!=0)    gx.add(i-1,to-1,1);
90                 else        gx.add(i-1,to-1,0);
91             }
92         }
93         gx.solve(a-1);
94         int ans=gx.getdist(b-1);
95         if(ans>1024) ans=-1;
96         printf("%d
",ans);
97     }
98     return 0;
99 }

View Code

Til the Cows Come Home http://poj.org/problem?id=2387

dij+priority queue o （elogv）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<stack>
 5 #include<algorithm>
 6 #define mt(a,b) memset(a,b,sizeof(a))
 7 using namespace std;
 8 typedef __int64 LL;
 9 const int inf=0x3f3f3f3f;
10 class Dijkstra { ///单源最短路 o(ME*log(MV))
11     typedef int typec;///边权的类型
12     static const int ME=4e3+10;///边的个数
13     static const int MV=1e3+10;///点的个数
14     struct Q {
15         int id;
16         typec w;
17         friend bool operator <(const Q &a,const Q &b) {
18             return a.w>b.w;
19         }
20     } now;
21     priority_queue<Q> q;
22     struct E {
23         int v,next;
24         typec w;
25     } e[ME];
26     int n,le,head[MV],u,v,i;
27     typec dist[MV],w;
28     bool used[MV];
29 public:
30     void init(int tn) {///传入点的个数
31         n=tn;
32         le=0;
33         for(i=0;i<=n;i++) head[i]=-1;
34     }
35     void add(int u,int v,typec w) {
36         e[le].v=v;
37         e[le].w=w;
38         e[le].next=head[u];
39         head[u]=le++;
40     }
41     void solve(int s) {///传入起点
42         for(i=0; i<=n; i++) {
43             used[i]=true;
44             dist[i]=inf;
45         }
46         dist[s]=0;
47         now.id=s;
48         now.w=0;
49         while(!q.empty()) q.pop();
50         q.push(now);
51         while(!q.empty()) {
52             now=q.top();
53             q.pop();
54             u=now.id;
55             if(used[u]) {
56                 used[u]=false;
57                 for(i=head[u]; ~i; i=e[i].next) {
58                     v=e[i].v;
59                     w=e[i].w;
60                     if(used[v]&&dist[v]>w+dist[u]) {
61                         dist[v]=w+dist[u];
62                         now.id=v;
63                         now.w=dist[v];
64                         q.push(now);
65                     }
66                 }
67             }
68         }
69     }
70     typec getdist(int id) {
71         return dist[id];
72     }
73 } gx;
74 int main(){
75     int m,n,u,v,w;
76     while(~scanf("%d%d",&m,&n)){
77         gx.init(n);
78         while(m--){
79             scanf("%d%d%d",&u,&v,&w);
80             gx.add(u,v,w);
81             gx.add(v,u,w);
82         }
83         gx.solve(1);
84         printf("%d
",gx.getdist(n));
85     }
86     return 0;
87 }

View Code

dij v^2

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<stack>
 5 #include<algorithm>
 6 #define mt(a,b) memset(a,b,sizeof(a))
 7 using namespace std;
 8 typedef __int64 LL;
 9 const int inf=0x3f3f3f3f;
10 class Dijkstra_Matrix { ///单源最短路 (邻接阵)o(MV^2)
11     typedef int typec;///边权的类型
12     static const int MV=1e3+10;///点的个数
13     int n,pre[MV],i,j,k;
14     typec mat[MV][MV],dist[MV];
15     bool vis[MV];
16 public:
17     void init(int tn) { ///传入点的个数
18         n=tn;
19         for(i=0; i<=n; i++)
20             for(j=0; j<=n; j++)
21                 mat[i][j]=i==j?0:inf;
22     }
23     void add(int u,int v,typec w) {
24         mat[u][v]=min(mat[u][v],w);
25     }
26     void solve(int s) { ///传入起点
27         for(i=0; i<=n; i++) {
28             dist[i]=inf;
29             vis[i]=false;
30             pre[i]=-1;
31         }
32         for(dist[s]=0,j=0; j<=n; j++) {
33             for(k=-1,i=0; i<=n; i++) {
34                 if(!vis[i]&&(k==-1||dist[i]<dist[k])) {
35                     k=i;
36                 }
37             }
38             for(vis[k]=true,i=0; i<=n; i++) {
39                 if(!vis[i]&&dist[k]+mat[k][i]<dist[i]) {
40                     dist[i]=dist[k]+mat[pre[i]=k][i];
41                 }
42             }
43         }
44     }
45     typec getdist(int id) {
46         return dist[id];
47     }
48 } gx;
49 int main(){
50     int m,n,u,v,w;
51     while(~scanf("%d%d",&m,&n)){
52         gx.init(n);
53         while(m--){
54             scanf("%d%d%d",&u,&v,&w);
55             gx.add(u,v,w);
56             gx.add(v,u,w);
57         }
58         gx.solve(1);
59         printf("%d
",gx.getdist(n));
60     }
61     return 0;
62 }

View Code

spfa o(2e)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<stack>
 5 #include<algorithm>
 6 #define mt(a,b) memset(a,b,sizeof(a))
 7 using namespace std;
 8 typedef __int64 LL;
 9 const int inf=0x3f3f3f3f;
10 class Spfa { ///单源最短路o(2*ME)
11     typedef int typec;///边权的类型
12     static const int ME=1000010;///边的个数
13     static const int MV=1000010;///点的个数
14     struct E {
15         int v,next;
16         typec w;
17     } e[ME];
18     int n,le,head[MV],inque[MV];
19     typec dist[MV];
20     bool used[MV];
21     queue<int> q;
22 public:
23     void init(int tn) { ///传入点的个数
24         n=tn;
25         le=0;
26         mt(head,-1);
27     }
28     void add(int u,int v,typec w) {
29         e[le].v=v;
30         e[le].w=w;
31         e[le].next=head[u];
32         head[u]=le++;
33     }
34     bool solve(int s) { ///传入起点，下标0开始,存在负环返回false
35         for(int i=0; i<n; i++) {
36             dist[i]=inf;
37             used[i]=true;
38             inque[i]=0;
39         }
40         used[s]=false;
41         dist[s]=0;
42         inque[s]++;
43         while(!q.empty()) q.pop();
44         q.push(s);
45         while(!q.empty()) {
46             int u=q.front();
47             q.pop();
48             used[u]=true;
49             for(int i=head[u]; ~i; i=e[i].next) {
50                 int v=e[i].v;
51                 if(dist[v]>dist[u]+e[i].w) {
52                     dist[v]=dist[u]+e[i].w;
53                     if(used[v]) {
54                         used[v]=false;
55                         q.push(v);
56                         inque[v]++;
57                         if(inque[v]>n) return false;
58                     }
59                 }
60             }
61         }
62         return true;
63     }
64     typec getdist(int id) {
65         return dist[id];
66     }
67 } gx;
68 int main(){
69     int m,n,u,v,w;
70     while(~scanf("%d%d",&m,&n)){
71         gx.init(n);
72         while(m--){
73             scanf("%d%d%d",&u,&v,&w);
74             gx.add(u-1,v-1,w);
75             gx.add(v-1,u-1,w);
76         }
77         gx.solve(0);
78         printf("%d
",gx.getdist(n-1));
79     }
80     return 0;
81 }

View Code

bell ford ve

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<stack>
 5 #include<algorithm>
 6 #define mt(a,b) memset(a,b,sizeof(a))
 7 using namespace std;
 8 typedef __int64 LL;
 9 const int inf=0x3f3f3f3f;
10 class Bellman_ford { ///单源最短路o(MV*ME)
11     typedef int typec;///边权的类型
12     static const int ME=1000010;///边的个数
13     static const int MV=1000010;///点的个数
14     struct E {
15         int u,v,next;
16         typec w;
17     } e[ME];
18     int n,le,head[MV];
19     bool used[MV];
20     typec dist[MV];
21 public:
22     void init(int tn) { ///传入点的个数
23         n=tn;
24         le=0;
25         mt(head,-1);
26     }
27     void add(int u,int v,typec w) {
28         e[le].u=u;
29         e[le].v=v;
30         e[le].w=w;
31         e[le].next=head[u];
32         head[u]=le++;
33     }
34     bool solve(int s) {  ///传入起点，下标0开始，为真最短路成功,为假存在负环
35         for(int i=0; i<n; i++) {
36             used[i]=true;
37             dist[i]=inf;
38         }
39         used[s]=false;
40         dist[s]=0;
41         for(int i=head[s]; ~i; i=e[i].next){
42             int v=e[i].v;
43             dist[v]=min(dist[v],e[i].w);
44         }
45         for(int i=1; i<n; i++) {
46             typec sma=inf;
47             int p;
48             for(int j=0; j<n; j++) {
49                 if(used[j]&&sma>dist[j]) {
50                     p=j;
51                     sma=dist[j];
52                 }
53             }
54             used[p]=false;
55             for(int j=head[p]; ~j; j=e[j].next) {
56                 int v=e[j].v;
57                 if(!used[v]) continue;
58                 dist[v]=min(dist[v],e[j].w+dist[e[j].u]);
59             }
60         }
61         bool flag=true;
62         int j;
63         for(j=0; flag&&j<=n; j++) {
64             flag=false;
65             for(int i=0; i<n; i++) {
66                 for(int k=head[i]; ~k; k=e[k].next) {
67                     if(dist[e[k].v]>e[k].w+dist[i]) {
68                         dist[e[k].v]=e[k].w+dist[i];
69                         flag=true;
70                     }
71                 }
72             }
73         }
74         return j<=n;
75     }
76     typec getdist(int id){
77         return dist[id];
78     }
79 }gx;
80 int main(){
81     int m,n,u,v,w;
82     while(~scanf("%d%d",&m,&n)){
83         gx.init(n);
84         while(m--){
85             scanf("%d%d%d",&u,&v,&w);
86             gx.add(u-1,v-1,w);
87             gx.add(v-1,u-1,w);
88         }
89         gx.solve(0);
90         printf("%d
",gx.getdist(n-1));
91     }
92     return 0;
93 }

View Code

Subway http://poj.org/problem?id=2502

dij+priority queue o （elogv）

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<queue>
  5 #include<stack>
  6 #include<algorithm>
  7 #define mt(a,b) memset(a,b,sizeof(a))
  8 using namespace std;
  9 typedef __int64 LL;
 10 const int inf=0x3f3f3f3f;
 11 const int M=210;
 12 class Dijkstra { ///单源最短路 o(ME*log(MV))
 13     typedef double typec;///边权的类型
 14     static const int ME=4e5+10;///边的个数
 15     static const int MV=2e3+10;///点的个数
 16     struct Q {
 17         int id;
 18         typec w;
 19         friend bool operator <(const Q &a,const Q &b) {
 20             return a.w>b.w;
 21         }
 22     } now;
 23     priority_queue<Q> q;
 24     struct E {
 25         int v,next;
 26         typec w;
 27     } e[ME];
 28     int n,le,head[MV],u,v,i;
 29     typec dist[MV],w;
 30     bool used[MV];
 31 public:
 32     void init(int tn) {///传入点的个数
 33         n=tn;
 34         le=0;
 35         for(i=0;i<=n;i++) head[i]=-1;
 36     }
 37     void add(int u,int v,typec w) {
 38         e[le].v=v;
 39         e[le].w=w;
 40         e[le].next=head[u];
 41         head[u]=le++;
 42     }
 43     void solve(int s) {///传入起点
 44         for(i=0; i<=n; i++) {
 45             used[i]=true;
 46             dist[i]=inf;
 47         }
 48         dist[s]=0;
 49         now.id=s;
 50         now.w=0;
 51         while(!q.empty()) q.pop();
 52         q.push(now);
 53         while(!q.empty()) {
 54             now=q.top();
 55             q.pop();
 56             u=now.id;
 57             if(used[u]) {
 58                 used[u]=false;
 59                 for(i=head[u]; ~i; i=e[i].next) {
 60                     v=e[i].v;
 61                     w=e[i].w;
 62                     if(used[v]&&dist[v]>w+dist[u]) {
 63                         dist[v]=w+dist[u];
 64                         now.id=v;
 65                         now.w=dist[v];
 66                         q.push(now);
 67                     }
 68                 }
 69             }
 70         }
 71     }
 72     typec getdist(int id) {
 73         return dist[id];
 74     }
 75 } gx;
 76 struct point{
 77     double x,y;
 78 }p[M];
 79 double a[M][M];
 80 int main() {
 81     int i,j,c,flag=0;
 82     scanf("%lf%lf%lf%lf",&p[0].x,&p[0].y,&p[1].x,&p[1].y);
 83     int n=2;
 84     while(~scanf("%lf%lf",&p[n].x,&p[n].y)) {
 85         if(p[n].x==-1&&p[n].y==-1) {
 86             flag=0;
 87             continue;
 88         }
 89         if(flag) {
 90             a[n][n-1]=sqrt((p[n].x-p[n-1].x)*(p[n].x-p[n-1].x)+(p[n].y-p[n-1].y)*(p[n].y-p[n-1].y))/40000.0;
 91             a[n-1][n]=a[n][n-1];
 92         }
 93         n++;
 94         flag=1;
 95     }
 96     for(i=0; i<n; i++) {
 97         for(j=0; j<n; j++) {
 98             if(i!=j&&a[i][j]==0.0) {
 99                 a[i][j]=sqrt((p[j].x-p[i].x)*(p[j].x-p[i].x)+(p[j].y-p[i].y)*(p[j].y-p[i].y))/10000.0;
100             }
101         }
102     }
103     gx.init(n);
104     for(i=0;i<n;i++){
105         for(j=0;j<n;j++){
106             gx.add(i,j,a[i][j]);
107         }
108     }
109     gx.solve(0);
110     printf("%0.0f
",60.0*gx.getdist(1));
111     return 0;
112 }

View Code

dij v^2

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<queue>
 5 #include<stack>
 6 #include<algorithm>
 7 #define mt(a,b) memset(a,b,sizeof(a))
 8 using namespace std;
 9 typedef __int64 LL;
10 const int inf=0x3f3f3f3f;
11 const int M=210;
12 class Dijkstra_Matrix { ///单源最短路 (邻接阵)o(MV^2)
13     typedef double typec;///边权的类型
14     static const int MV=2e2+10;///点的个数
15     int n,pre[MV],i,j,k;
16     typec mat[MV][MV],dist[MV];
17     bool vis[MV];
18 public:
19     void init(int tn) { ///传入点的个数
20         n=tn;
21         for(i=0; i<=n; i++)
22             for(j=0; j<=n; j++)
23                 mat[i][j]=i==j?0:inf;
24     }
25     void add(int u,int v,typec w) {
26         mat[u][v]=min(mat[u][v],w);
27     }
28     void solve(int s) { ///传入起点
29         for(i=0; i<=n; i++) {
30             dist[i]=inf;
31             vis[i]=false;
32             pre[i]=-1;
33         }
34         for(dist[s]=0,j=0; j<=n; j++) {
35             for(k=-1,i=0; i<=n; i++) {
36                 if(!vis[i]&&(k==-1||dist[i]<dist[k])) {
37                     k=i;
38                 }
39             }
40             for(vis[k]=true,i=0; i<=n; i++) {
41                 if(!vis[i]&&dist[k]+mat[k][i]<dist[i]) {
42                     dist[i]=dist[k]+mat[pre[i]=k][i];
43                 }
44             }
45         }
46     }
47     typec getdist(int id) {
48         return dist[id];
49     }
50 } gx;
51 struct point{
52     double x,y;
53 }p[M];
54 double a[M][M];
55 int main() {
56     int i,j,c,flag=0;
57     scanf("%lf%lf%lf%lf",&p[0].x,&p[0].y,&p[1].x,&p[1].y);
58     int n=2;
59     while(~scanf("%lf%lf",&p[n].x,&p[n].y)) {
60         if(p[n].x==-1&&p[n].y==-1) {
61             flag=0;
62             continue;
63         }
64         if(flag) {
65             a[n][n-1]=sqrt((p[n].x-p[n-1].x)*(p[n].x-p[n-1].x)+(p[n].y-p[n-1].y)*(p[n].y-p[n-1].y))/40000.0;
66             a[n-1][n]=a[n][n-1];
67         }
68         n++;
69         flag=1;
70     }
71     for(i=0; i<n; i++) {
72         for(j=0; j<n; j++) {
73             if(i!=j&&a[i][j]==0.0) {
74                 a[i][j]=sqrt((p[j].x-p[i].x)*(p[j].x-p[i].x)+(p[j].y-p[i].y)*(p[j].y-p[i].y))/10000.0;
75             }
76         }
77     }
78     gx.init(n);
79     for(i=0;i<n;i++){
80         for(j=0;j<n;j++){
81             gx.add(i,j,a[i][j]);
82         }
83     }
84     gx.solve(0);
85     printf("%0.0f
",60.0*gx.getdist(1));
86     return 0;
87 }

View Code

spfa(2e)

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<queue>
  5 #include<stack>
  6 #include<algorithm>
  7 #define mt(a,b) memset(a,b,sizeof(a))
  8 using namespace std;
  9 typedef __int64 LL;
 10 const int inf=0x3f3f3f3f;
 11 const int M=210;
 12 class Spfa { ///单源最短路o(2*ME)
 13     typedef double typec;///边权的类型
 14     static const int ME=M*M;///边的个数
 15     static const int MV=M;///点的个数
 16     struct E {
 17         int v,next;
 18         typec w;
 19     } e[ME];
 20     int n,le,head[MV],inque[MV];
 21     typec dist[MV];
 22     bool used[MV];
 23     queue<int> q;
 24 public:
 25     void init(int tn) { ///传入点的个数
 26         n=tn;
 27         le=0;
 28         mt(head,-1);
 29     }
 30     void add(int u,int v,typec w) {
 31         e[le].v=v;
 32         e[le].w=w;
 33         e[le].next=head[u];
 34         head[u]=le++;
 35     }
 36     bool solve(int s) { ///传入起点，下标0开始,存在负环返回false
 37         for(int i=0; i<n; i++) {
 38             dist[i]=inf;
 39             used[i]=true;
 40             inque[i]=0;
 41         }
 42         used[s]=false;
 43         dist[s]=0;
 44         inque[s]++;
 45         while(!q.empty()) q.pop();
 46         q.push(s);
 47         while(!q.empty()) {
 48             int u=q.front();
 49             q.pop();
 50             used[u]=true;
 51             for(int i=head[u]; ~i; i=e[i].next) {
 52                 int v=e[i].v;
 53                 if(dist[v]>dist[u]+e[i].w) {
 54                     dist[v]=dist[u]+e[i].w;
 55                     if(used[v]) {
 56                         used[v]=false;
 57                         q.push(v);
 58                         inque[v]++;
 59                         if(inque[v]>n) return false;
 60                     }
 61                 }
 62             }
 63         }
 64         return true;
 65     }
 66     typec getdist(int id) {
 67         return dist[id];
 68     }
 69 } gx;
 70 struct point{
 71     double x,y;
 72 }p[M];
 73 double a[M][M];
 74 int main() {
 75     int i,j,c,flag=0;
 76     scanf("%lf%lf%lf%lf",&p[0].x,&p[0].y,&p[1].x,&p[1].y);
 77     int n=2;
 78     while(~scanf("%lf%lf",&p[n].x,&p[n].y)) {
 79         if(p[n].x==-1&&p[n].y==-1) {
 80             flag=0;
 81             continue;
 82         }
 83         if(flag) {
 84             a[n][n-1]=sqrt((p[n].x-p[n-1].x)*(p[n].x-p[n-1].x)+(p[n].y-p[n-1].y)*(p[n].y-p[n-1].y))/40000.0;
 85             a[n-1][n]=a[n][n-1];
 86         }
 87         n++;
 88         flag=1;
 89     }
 90     for(i=0; i<n; i++) {
 91         for(j=0; j<n; j++) {
 92             if(i!=j&&a[i][j]==0.0) {
 93                 a[i][j]=sqrt((p[j].x-p[i].x)*(p[j].x-p[i].x)+(p[j].y-p[i].y)*(p[j].y-p[i].y))/10000.0;
 94             }
 95         }
 96     }
 97     gx.init(n);
 98     for(i=0;i<n;i++){
 99         for(j=0;j<n;j++){
100             gx.add(i,j,a[i][j]);
101         }
102     }
103     gx.solve(0);
104     printf("%0.0f
",60.0*gx.getdist(1));
105     return 0;
106 }

View Code

bell ford ve

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<queue>
  5 #include<stack>
  6 #include<algorithm>
  7 #define mt(a,b) memset(a,b,sizeof(a))
  8 using namespace std;
  9 typedef __int64 LL;
 10 const int inf=0x3f3f3f3f;
 11 const int M=210;
 12 class Bellman_ford { ///单源最短路o(MV*ME)
 13     typedef double typec;///边权的类型
 14     static const int ME=M*M;///边的个数
 15     static const int MV=M;///点的个数
 16     struct E {
 17         int u,v,next;
 18         typec w;
 19     } e[ME];
 20     int n,le,head[MV];
 21     bool used[MV];
 22     typec dist[MV];
 23 public:
 24     void init(int tn) { ///传入点的个数
 25         n=tn;
 26         le=0;
 27         mt(head,-1);
 28     }
 29     void add(int u,int v,typec w) {
 30         e[le].u=u;
 31         e[le].v=v;
 32         e[le].w=w;
 33         e[le].next=head[u];
 34         head[u]=le++;
 35     }
 36     bool solve(int s) {  ///传入起点，下标0开始，为真最短路成功,为假存在负环
 37         for(int i=0; i<n; i++) {
 38             used[i]=true;
 39             dist[i]=inf;
 40         }
 41         used[s]=false;
 42         dist[s]=0;
 43         for(int i=head[s]; ~i; i=e[i].next){
 44             int v=e[i].v;
 45             dist[v]=min(dist[v],e[i].w);
 46         }
 47         for(int i=1; i<n; i++) {
 48             typec sma=inf;
 49             int p;
 50             for(int j=0; j<n; j++) {
 51                 if(used[j]&&sma>dist[j]) {
 52                     p=j;
 53                     sma=dist[j];
 54                 }
 55             }
 56             used[p]=false;
 57             for(int j=head[p]; ~j; j=e[j].next) {
 58                 int v=e[j].v;
 59                 if(!used[v]) continue;
 60                 dist[v]=min(dist[v],e[j].w+dist[e[j].u]);
 61             }
 62         }
 63         bool flag=true;
 64         int j;
 65         for(j=0; flag&&j<=n; j++) {
 66             flag=false;
 67             for(int i=0; i<n; i++) {
 68                 for(int k=head[i]; ~k; k=e[k].next) {
 69                     if(dist[e[k].v]>e[k].w+dist[i]) {
 70                         dist[e[k].v]=e[k].w+dist[i];
 71                         flag=true;
 72                     }
 73                 }
 74             }
 75         }
 76         return j<=n;
 77     }
 78     typec getdist(int id){
 79         return dist[id];
 80     }
 81 }gx;
 82 struct point{
 83     double x,y;
 84 }p[M];
 85 double a[M][M];
 86 int main() {
 87     int i,j,c,flag=0;
 88     scanf("%lf%lf%lf%lf",&p[0].x,&p[0].y,&p[1].x,&p[1].y);
 89     int n=2;
 90     while(~scanf("%lf%lf",&p[n].x,&p[n].y)) {
 91         if(p[n].x==-1&&p[n].y==-1) {
 92             flag=0;
 93             continue;
 94         }
 95         if(flag) {
 96             a[n][n-1]=sqrt((p[n].x-p[n-1].x)*(p[n].x-p[n-1].x)+(p[n].y-p[n-1].y)*(p[n].y-p[n-1].y))/40000.0;
 97             a[n-1][n]=a[n][n-1];
 98         }
 99         n++;
100         flag=1;
101     }
102     for(i=0; i<n; i++) {
103         for(j=0; j<n; j++) {
104             if(i!=j&&a[i][j]==0.0) {
105                 a[i][j]=sqrt((p[j].x-p[i].x)*(p[j].x-p[i].x)+(p[j].y-p[i].y)*(p[j].y-p[i].y))/10000.0;
106             }
107         }
108     }
109     gx.init(n);
110     for(i=0;i<n;i++){
111         for(j=0;j<n;j++){
112             gx.add(i,j,a[i][j]);
113         }
114     }
115     gx.solve(0);
116     printf("%0.0f
",60.0*gx.getdist(1));
117     return 0;
118 }

View Code

end