1421：Floyd
时间限制: 1000 ms 内存限制: 131072 KB
【题目描述】
给定一个n个点m条边的有向图。Dis(a,b)表示a到b的最短距离，如果a无法到b,则Dis(a,b)=10^16,规定 Dis(a,a)=0。
读懂以下程序，并输出S。
long long S,f=1e16;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
S^=Dis(i,j)+f;
【输入】
第一行两个整数n,m,代表点数和边数； 接下来m行，每行三个整数s,t,d,代表从s到t有一条长度为d的有向边。
【输出】
输出一个整数表示S。
【输入样例】
2 3
1 2 1
1 2 3
2 2 0
【输出样例】
28300427233787905
【提示】
数据规模及约定
N≤500,0≤M≤250000,1≤S,T≤N,−10^9≤D≤10^9
保证没有负环。
1. #include <bits/stdc++.h> 2. using namespace std; 3. long long dist[505][505]; 4. long long n,m; 5. long long s,t,d; 6. void Floyd(){//搜索路径 7. for(int k=1;k<=n;k++) 8. for(int i=1;i<=n;i++) 9. for(int j=1;j<=n;j++) 10. if(dist[i][k]!=1e16 && dist[k][j]!=1e16) 11. dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); 12. } 13. int main() { 14. cin>>n>>m; 15. for(int i=1;i<=n;i++) 16. for(int j=1;j<=n;j++) 17. if(i==j) dist[i][j]=0; 18. else dist[i][j]=1e16; 19. for(int i=1;i<=m;i++){ 20. cin>>s>>t>>d; 21. dist[s][t]=min(dist[s][t],d); 22. } 23. Floyd(); 24. long long s=0; 25. for(int i=1;i<=n;i++) 26. for(int j=1;j<=n;j++) 27. s ^=(dist[i][j]+(long long)(1e16)); 28. cout<<s; 29. return 0; 30. }
