  Code
1 //f[i][j][k]如果表示从节点i到j经过k条边的最短路则：
2//f[i][j][k]=max{f[i][j][k],f[i][t][k/2]+f[t][j][(k+1)/2]}
3//求解时采用倍增法才可以通过：其中先求f[i][j][1]，再求f[i][j][2]……再求f[i][j][k],再求f[i][j][2*k]或者f[i][j][2*k+1]
4//对n采用二进制表示后可根据其串来决定求出f[i][j][k]后再求f[i][j][2*k]还是求f[i][j][2*k+1]
5//很经典
6//poj 3613
7
8#include<iostream>
9#include<vector>
10#include<queue>
11
12using namespace std;
13
14const int maxn = 1001;
15const int nil = INT_MAX/2;
16
17int map[maxn][maxn];
18vector<int>ver;
19bool usd[maxn];
20bool mk[maxn];
21int minv,maxv;
22int next[maxn][maxn],ans[maxn][maxn];
23
24int Min(int a,int b,int c)
25 {
26 int d = nil;
27 d = a > d ? d : a;
28 d = b > d ? d : b;
29 d = c > d ? d : c;
30 return d;
31 }
32
33int Max(int a,int b,int c)
34{
35 int d = -1;
36 d = a < d ? d : a;
37 d = b < d ? d : b;
38 d = c < d ? d : c;
39 return d;
40}
41
42void floyd(int dis[][maxn],int map[][maxn],int ans[][maxn])
43{
44 int i,j,k,s,e,tv;
45 for(i = 0;i < ver.size(); ++i)
46 for(j = 0;j < ver.size(); ++j)
47 for(k = 0;k < ver.size(); ++k)
48  {
49 tv = ver[i];s = ver[j];e = ver[k];
50 if(dis[s][e] > map[s][tv] + ans[tv][e])
51 dis[e][s] = dis[s][e] = map[s][tv] + ans[tv][e];
52 }
53}
54
55void copy(int a[][maxn],int b[][maxn])
56{
57 int i,j,s,e;
58 for(i = 0;i < ver.size(); ++i)
59 for(j = 0;j < ver.size(); ++j)
60 {
61 s = ver[i];e = ver[j];
62 a[s][e] = b[s][e];
63 b[s][e] = nil;
64 }
65}
66
67void solve(int n)
68{
69 int i,j,s,e;
70 int t;
71 int flag[32];
72
73 for(i = 0;i < ver.size(); ++i)
74 {
75 for(j = 0;j < ver.size(); ++j)
76 {
77 s = ver[i];e = ver[j];
78 dis[s][e] = ans[s][e] = next[s][e] = nil;
79 }
80 ans[ver[i]][ver[i]] = 0;
81 }
82 t=0;
83 while(n)
84 {
85 if(n%2)
86 {
87 flag[t++]=1;
88 }
89 else flag[t++]=0;
90 n/=2;
91 }
92 for(i=t-1;i>=0;i--)
93 {
94 floyd(next,ans,ans);
95 copy(ans,next);
96 if(flag[i])
97 {
98 floyd(next,ans,map);
99 copy(ans,next);
100 }
101 }
102}
103
104int main()
105{
106// freopen("data.txt","r",stdin);
107 int N,T,S,E;
108 int a,b,i,j,c;
109
110 while(scanf("%d%d%d%d",&N,&T,&S,&E) != EOF)
111 {
112 minv = nil,maxv = -1;
113 memset(usd,0,sizeof(usd));
114 ver.clear();
115 for(i = 1;i < 1001;++i)
116 for(j = 1;j < 1001;++j)
117 map[i][j] = nil;
118
119 usd[S] = 1;ver.push_back(S);
120 minv = Min(minv,S,E);
121 maxv = Max(maxv,S,E);
122 if(!usd[E])
123 {
124 usd[E] = 1;
125 ver.push_back(E);
126 }
127
128 while(T--)
129 {
130 scanf("%d%d%d",&a,&b,&c);
131 map[b][c] = map[b][c] > a ? a : map[b][c];
132 map[c][b] = map[b][c];
133
134 if(!usd[c])
135 {
136 usd[c] = 1;
137 ver.push_back(c);
138 }
139 if(!usd[b])
140 {
141 usd[b] = 1;
142 ver.push_back(b);
143 }
144 minv = Min(minv,b,c);
145 maxv = Max(maxv,b,c);
146 }
147
148 solve(N);
149 printf("%d\n",ans[S][E]);
150 }
151 return 0;
152}
153
|
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 24 | 25 | 26 | 27 | 28 | 29 | 30 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | 8 | 9 | 10 | 11 | 12 | 13 | 14 | | 15 | 16 | 17 | 18 | 19 | 20 | 21 | | 22 | 23 | 24 | 25 | 26 | 27 | 28 | | 29 | 30 | 31 | 1 | 2 | 3 | 4 |
|
导航
统计
常用链接
留言簿
随笔分类(1)
随笔档案(2)
文章分类(15)
文章档案(7)
搜索
最新评论
阅读排行榜
评论排行榜
|
|