首页 > 代码库 > zoj3080 ChiBi --- floyd求连通块内最短路
zoj3080 ChiBi --- floyd求连通块内最短路
此题最大最小搞的太复杂。。。并查集维护连通块,连通块内floyd就可以了
#include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #define inf 0x3f3f3f3f #define eps 1e-6 #define ll __int64 using namespace std; vector<int> part[1010]; int mp[1010][1010],n,r[1010],t[1010],vis[1010],dis[1010][1010]; int root(int a) { if(r[a]==a) return a; return r[a]=root(r[a]); } void merge(int a,int b) { int ra=root(a); int rb=root(b); if(ra!=rb) r[ra]=rb; } int floyd(int s) { int m,i,j,k,mmax,mmin; m=part[s].size(); for(i=0;i<m;i++) { for(j=0;j<m;j++) { int a=part[s][i]; int b=part[s][j]; dis[i][j]=mp[a][b]==-1?inf:mp[a][b]; } } for(k=0;k<m;k++) for(i=0;i<m;i++) for(j=0;j<m;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); mmin=inf; for(i=0;i<m;i++) { mmax=0; for(j=0;j<m;j++) mmax=max(mmax,dis[i][j]); mmin=min(mmin,mmax+t[part[s][i]]); } return mmin; } int main() { int i,j,ans[1010]; while(~scanf("%d",&n)) { for(i=0;i<=n;i++) { r[i]=i; part[i].clear(); } for(i=0;i<n;i++) for(j=0;j<n;j++) { scanf("%d",&mp[i][j]); if(mp[i][j]!=-1) merge(i,j); } for(i=0;i<n;i++) scanf("%d",&t[i]); for(i=0;i<n;i++) part[root(i)].push_back(i); memset(vis,0,sizeof vis); int aa=0; for(i=0;i<n;i++) { int tmp=root(i); if(!vis[tmp]) { vis[tmp]=1; aa=max(aa,floyd(tmp)); } } printf("%d\n",aa); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。