最近做了两道floyd变种的题目,又加深了对floyd原理的理解.
第2题: tju 3214 Find the Path
http://acm.tju.edu.cn/toj/showp3214.html
题目大意是给一个无向图,每个结点有个点权c[p]
对于查询的点对i,j和权k,求在中间节点(不包含端点i,j)权值不大于k的限制下,i,j间最短路径.
由于查询次数多,因此一次查询复杂度需要在O(logn)以内.考虑计算出所有点对在所有限制条件下的最短路,O(1)查询.
限制条件不作用于端点i,j,正好可以用floyd解决.因为floyd正是不断向中间点集中加入点.只要限制一下这些被加入点的条件,就可以解决这题了.
初步归纳,对于查询i,j,k,应该输出将所有c[p]<=k的点加入后的floyd[i,j]
对于限制k,点集的情况是:加了权最小的m个(0<=m<=N),这些点的权都不超过k
因此将点按权值升序排列.dist[k][i][j]表示:前k个点被加入后,i,j间的最短路.
代码如下:
1
#include <iostream>
2
using namespace std;
3
int T,N,M,Q,pc[210];
4
int C[210],dist[210][210][210];
5![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool mycmp(int a, int b)
{
6
return (C[a]<C[b]);
7
}
8![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
9
int i,j,k,p,a,b,c;
10
scanf("%d",&T);
11![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(T--)
{
12
memset(dist,0xff,sizeof(dist));
13
scanf("%d%d",&N,&M);
14
C[pc[0]=0]=-1;
15![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1;i<=N;i++)
{
16
scanf("%d",&C[i]);
17
pc[i]=i;
18
}
19
sort(pc,pc+N+1,mycmp);
20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1; i<=M; i++)
{
21
scanf("%d%d%d",&a,&b,&c);
22
dist[0][a+1][b+1]=c;
23
dist[0][b+1][a+1]=c;
24
}
25
//floyd
26![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(k=1; k<=N; k++)
{
27
p=pc[k];
28![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1; i<=N; i++)
{
29![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j=1; j<=N; j++)
{
30
if(dist[k][i][j]<0)
31
dist[k][i][j]=dist[k-1][i][j];
32
else if(dist[k-1][i][j]>=0)
33
dist[k][i][j]=min(dist[k][i][j],dist[k-1][i][j]);
34
35![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(i!=j && dist[k-1][i][p]>=0 && dist[k-1][p][j]>=0)
{
36
if(dist[k][i][j]<0)
37
dist[k][i][j]=dist[k-1][i][p]+dist[k-1][p][j];
38
else
39
dist[k][i][j]=min(dist[k][i][j], dist[k-1][i][p]+dist[k-1][p][j]);
40
}
41
//printf("%d,%d,%d(%d) ",k,i,j,dist[k][i][j]);
42
}
43
}
44
}
45
//query
46
scanf("%d",&Q);
47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(Q--)
{
48
scanf("%d%d%d",&a,&b,&c);
49
//顺序查找
50
for(i=0; i<=N && C[pc[i]]<=c; i++);
51
printf("%d\n",dist[i-1][a+1][b+1]);
52
}
53
printf("\n");
54
}
55
return 0;
56
}
57![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2009-03-31 14:39
wolf5x 阅读(231)
评论(0) 编辑 收藏 引用 所属分类:
acm_icpc 、
algorithm