题目描述

给定一个n个点m条边的有向图。Dis(a,b)表示a到b的最短距离，如果a无法到b,则Dis(a,b)=10^16,规定 Dis(a,a)=0。

读懂以下程序，并输出S。

int S=0;long long 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,−109≤D≤1e9N≤500,0≤M≤250000,1≤S,T≤N,−109≤D≤1e9

保证没有负环

时间限制:1s

空间限制:256M

        真是一道前无古人的Floyd。不得不Orz……

        果然还是太NaÏve了……

        注意到题目可以有负权边。所以要考虑这样一种情况：

        假设有一个图

        那么Floyd算法会把图看成这样：

        好了，那么现在我们来愉快的模拟一下。当中转点为(2),1->3被操作时。dis[1,3]就名正言顺地变成了inf-1。而1,3本来是不联通的。如果用dis==inf判断不连通，岂不GG？

        所以，我们只要把inf初始化成MAX_longlong/2，将判断条件设置成>1e16即可（貌似也有人拿1e17过了）

#include<cstdio>
#include<cstring>
#define min(a,b) (a>b?b:a)
#define ll long long
using namespace std;
ll map[550][550];
inline ll read(){/*读入优化，飞天*/
    ll ret=0,f=1;
    char c=getchar();
    while(c>'9' || c<'0'){
    	if(c=='-')	f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9')
        ret=ret*10+c-'0',c=getchar();
    return ret*f;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	ll inf=9223372036854775807LL/2;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			map[i][j]=inf;
	for(int i=1;i<=m;i++){
		ll u,v,w;
		u=read(),v=read(),w=read();
		map[u][v]=min(map[u][v],w);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				map[j][k]=min(map[j][i]+map[i][k],map[j][k]);
				
	for(int i=1;i<=n;i++)
		map[i][i]=0;
	ll S=0,f=1LL*1e16;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(map[i][j]>f) S^=(f+f);
			else S^=(map[i][j]+f);
		}
	printf("%lld\n",S);
	return 0;
}