相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4773
神犇题解:http://www.cnblogs.com/lytccc/p/6616625.html
解题报告
我们可以使用倍增Floyd来解决这个问题
具体来讲:
我们从大到小维护走$2^k$步后的最短路
如果出现负环,那么不继承,舍弃掉更改
如果没有出现负环,那么更新数组
时间复杂度:$O(n^3 \log n)$
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4773
神犇题解:http://www.cnblogs.com/lytccc/p/6616625.html
我们可以使用倍增Floyd来解决这个问题
具体来讲:
我们从大到小维护走$2^k$步后的最短路
如果出现负环,那么不继承,舍弃掉更改
如果没有出现负环,那么更新数组
时间复杂度:$O(n^3 \log n)$
题目传送门:http://codevs.cn/problem/1817/
这题可以说是Floyd的最终考验吧?
具体来说:做了这题Floyd的原理就完全明白了吧!
详细请参考《算导》P405吧!(难得算导说了一次人话)
#include<iostream> #include<cstdio> #include<vector> #define INF 1000099 using namespace std; struct abc{int point,len;}; int n,m; int t[299]={0}; int f[299][299]; bool yet[299]={0}; vector<abc> path[299]; bool day[100099]={0}; int pro=0; void init(){ for (int i=1;i<=250;i++){ t[i]=INF; } for (int i=0;i<=250;i++){ for (int j=0;j<=250;j++){ f[i][j]=INF; } } scanf("%d%d",&n,&m); for (int i=1;i<=n;i++){ scanf("%d",&t[i]); if (t[i]==0) yet[i]=true; } abc hc; for (int i=1,a,b,leng;i<=m;i++){ scanf("%d%d%d",&a,&b,&leng); a++;b++; f[a][b]=leng;f[b][a]=leng; hc.point=b;hc.len=leng; path[a].push_back(hc); hc.point=a; path[b].push_back(hc); } } void update(int num){ int end,length; for (int k=pro+1;k<=end;k++) yet[k]=true; for (int k=pro+1;k<=end;k++){ for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ f[i][j]=min(f[i][j],f[i][k]+f[k][j]); } } } pro=end; } int main(){ int Q,x,y,ti; init(); cin>>Q; for (int i=1;i<=Q;i++){ scanf("%d%d%d",&x,&y,&ti); x++;y++; if (!day[ti]) { update(ti); day[ti]=1; } if (f[x][y]<INF && yet[x] && yet[y]) printf("%d\n",f[x][y]); else printf("-1\n"); } return 0; }
为什么去年写的代码这么丑? (╯‵□′)╯︵┻━┻