首页 > 代码库 > AC日记——灾后重建 洛谷 P1119
AC日记——灾后重建 洛谷 P1119
灾后重建
思路：
看到n<=200，思考弗洛伊德算法；
如何floyed呢？
floyed是一种动态规划求最短路的算法；
它通过枚举中间点来更新两点之间最短路；
回到这个题本身；
所有点的重建完成的时间和询问的时间都已经排好序了；
所以，我们把floyed拆开；
对于一个三维的k，i，j的floyed算法；
我们判断当前的询问在哪两个相邻的k之间；
然后，我们判断当时的连通性以及最短路情况；
来，上代码：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define INF 0x7ffffffint n,m,f[205][205][205],ti[205];inline void in(int &now){ char Cget=getchar();now=0; while(Cget>‘9‘||Cget<‘0‘) Cget=getchar(); while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); }}int main(){ in(n),in(m); for(int k=0;k<=n+2;k++) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) f[k][i][j]=INF; } } for(int i=0;i<n;i++) in(ti[i]); int u,v,w; for(int i=1;i<=m;i++) { in(u),in(v),in(w); f[0][u][v]=w; f[0][v][u]=w; } for(int k=1;k<=n;k++) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k-1]+f[k-1][k-1][j]); } } } in(m);int tot=1; for(int i=1;i<=m;i++) { in(u),in(v),in(w); if(ti[u]>w||ti[v]>w) { printf("-1\n"); continue; } while(ti[tot]<=w&&tot<n) tot++; int now=tot-1; if(ti[now]<=w) { if(f[tot][u][v]==INF) printf("-1\n"); else printf("%d\n",f[tot][u][v]); } else printf("-1\n"); } return 0;}
AC日记——灾后重建 洛谷 P1119
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。