洛谷 P1111 修复公路
程序员文章站
2022-03-20 21:13:51
[TOC] 题目 "P1111 修复公路" 思路 跑一边$\text{prim}$,然后找到最大值,如果有这等于$inf$输出 $Code$ cpp include include include include include define max_(a,b) a b?a:b; using nam ......
目录
题目
思路
跑一边$\text{prim}$,然后找到最大值,如果有这等于$inf$输出-1
$code$
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #define max_(a,b) a>b?a:b; using namespace std; const int inf=1061109567; int n,m; bool vis[5001]; int map[5001][5001],dis[5001]; inline int read(){ int x=0; bool f=0; char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return f?-x:x; } void prim(){ for(int i=1;i<=n;++i){ int k=0; for(int j=1;j<=n;++j){ if(!vis[j]&&dis[j]<dis[k]) k=j; } vis[k]=1; for(int j=1;j<=n;++j){ if(!vis[j]&&map[k][j]<dis[j]){ dis[j]=map[k][j]; } } } } int main(){ memset(map,0x3f3f3f,sizeof(map)); memset(dis,0x3f3f3f,sizeof(dis)); dis[1]=0; n=read(),m=read(); int x,y,w; for(int i=1;i<=m;++i){ x=read(),y=read(),w=read(); if(w<map[x][y]){ map[x][y]=w,map[y][x]=w; } } prim(); int ans=0; for(int i=1;i<=n;++i){ if(dis[i]==inf){ printf("-1\n"); return 0; }else ans=max_(ans,dis[i]); } cout<<ans; return 0; }
下一篇: centos源码编译安装新版本内核