首页 > 代码库 > CF400D最短路

CF400D最短路

2024-07-16 14:32:07   221人阅读

题意：给你n个点，是否可以分成k块，如果可以分，就求任意两块之间的最短路。如果两点距离为0即为一块，但是还有一个条件，我一开始没看清，

以为只要是可以满足K块就行，与先后顺序无关，其实不然。如果是分成3块，第一块是5，第二块是3，第三块是4，那么1到5号点都是第一块的，

6到8号点时第二块的，9到11号点是第三块的，如果不满足这种就是错误的。有点坑啊，英语是硬伤啊！！！！！

思路：先用并查集如果满足w=0；那么就是一个集合，再按顺序求出那些点应该是在那个块。再求块到块之间如果有路径，就保存最短的那条，

判断是不是都满足分块的要求，如果满足，就跑一次Floyd，求得任意两块之间的距离。

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxm = 100009;const int maxn = 600;const int inf = 1<<29;struct node{	int u,v,w;}eg[maxm];int fa[maxm];int dis[maxn][maxn];int Count[maxn]; int hash[maxn];int sum[maxn];int n,m,k;int pre[maxm];void init(){	int i,j;	for(i=0; i<= n; i++) fa[i] = -1;	for(i =0;i<maxn;i++)	{		for(j=0;j<maxn;j++)			dis[i][j] = inf;		dis[i][i] = 0;		}}int find(int x){	int p;	for(p =x;fa[p] >= 0;p  = fa[p]);	while(x != p)	{		int temp = fa[x];		fa[x] = p;		x = temp;	}	return p;}void Union(int a,int b){	int x = find(a);	int y = find(b);	if(x == y) return ;	int temp = fa[x] + fa[y];	if(fa[x] > fa[y])		fa[x] = y, fa[y] = temp;	else		fa[y] = x, fa[x] = temp;}void floyd(){	for(int z =0; z < k; z++)	{		for(int i= 0; i < k; i++)		{			for(int j = 0;j < k; j++)			{				if(dis[i][j] > dis[i][z] + dis[z][j])					dis[i][j] = dis[i][z] + dis[z][j];			}		}	}}inline int min(int a,int b){return a < b ? a : b;}int main(){	int i;	while(~scanf("%d%d%d",&n,&m,&k))	{		init();			sum[0] = 0;		for(i=1;i<=k;i++)		{			scanf("%d",&Count[i]);			sum[i] =sum[i-1] + Count[i];		}		for(i=0;i<m;i++)		{			scanf("%d%d%d",&eg[i].u,&eg[i].v,&eg[i].w);			if(eg[i].w == 0)				Union(eg[i].u,eg[i].v);			int u=lower_bound(sum+1,sum+k+1,eg[i].u)-sum;			u--;            int v=lower_bound(sum+1,sum+k+1,eg[i].v)-sum;			v--;			if(u == v)continue;					dis[u][v] = dis[v][u] = min(dis[u][v],eg[i].w);		}	    memset(pre,0,sizeof(pre));        int flag=1;        for(i=1;i<=n;i++)        {            int posu=lower_bound(sum+1,sum+k+1,i)-sum;            int u=find(i);            if(pre[posu])            {                if(u!=pre[posu])                {                    flag=0;                    break ;                }            }            else            {                pre[posu]=u;            }        }        if(flag) printf("Yes\n");        else        {            printf("No\n");            continue ;        }		floyd();		for(i=0;i<k;i++)		{			for(int j=0; j < k;j++)			{				if(dis[i][j] >= inf)dis[i][j] = -1;				printf("%d ",dis[i][j]);			}			printf("\n");		}	}	return 0;}

 


联系
我们