文章详情

  • 游戏榜单
  • 软件榜单
关闭导航
热搜榜
热门下载
热门标签
php爱好者> php文档>codeforces beta round #25 c题 roads in berland...

codeforces beta round #25 c题 roads in berland...

时间:2010-08-15  来源:lyhypacm

这题很囧的7、8次WA都贡献给了I64d。。。好吧我承认这个CF很强大。。。

这题的思路如下:

首先用Floyd在O(n^3)的时间复杂度内算出最短路总和ret

更新的边(x,y)长度是w,那么如果w>=dist[x][y]就不做处理,输出这时的ret

如果w<dist[x][y],那么枚举所有的结点,对结点j和k

dist[j][k]的值就是dist[j][k]、dist[j][x]+w+dist[y][k]和dist[j][y]+w+dist[x][k]中的最小值。

如果dist[j][k]的新值比原来的小,那么就更新ret的值。

为了优化时间,让j大于i,更新了dist[j][k]后顺便把dist[k][j]更新了

dist[k][j]=dist[j][k]

我的代码:

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; typedef long long LL; const int MAX=310; int p,q,k,n; LL dist[MAX][MAX]; void Floyd() { for(k=1;k<=n;k++) for(p=1;p<=n;p++) for(q=1;q<=n;q++) if (dist[p][q]-dist[p][k]>dist[k][q]) dist[p][q]=dist[p][k]+dist[k][q]; } int main() { int m; int x,y,w,tmp; LL ret=0; scanf("%d",&n); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%I64d",&dist[i][j]); } } Floyd(); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) ret+=dist[i][j]; scanf("%d",&m); for(int i=0;i<m;i++) { scanf("%d%d%d",&x,&y,&w); if(x>y) swap(x,y); if(w<dist[x][y]) { for(int j=1;j<=n;j++) { for(int k=j+1;k<=n;k++) { tmp=dist[j][k]; if(dist[j][x]+w+dist[y][k]<dist[j][k]) dist[j][k]=dist[j][x]+w+dist[y][k]; if(dist[j][y]+w+dist[x][k]<dist[j][k]) dist[j][k]=dist[j][y]+w+dist[x][k]; if(dist[j][k]<tmp) { ret-=tmp-dist[j][k]; dist[k][j]=dist[j][k]; } } } } if(i) printf(" "); printf("%I64d",ret); } printf("\n"); return 0; }

总结:关于最短路中改变一条边权值的问题,可以通过边的两个顶点来进行更新

相关阅读 更多 +
排行榜 更多 +
辰域智控app

辰域智控app

系统工具 下载
网医联盟app

网医联盟app

运动健身 下载
汇丰汇选App

汇丰汇选App

金融理财 下载