6005 - Graph

如果一条一条路算的话非常不好去重，不妨一条一条边算

30pts:先跑一遍Floyd预处理，枚举点对和每条边，O(1)判断边是否在点对的最短路上，总时间复杂度O(n^2m)

100pts:考虑优化上述解法，每次就不用枚举n^2条边：预处理以k为端点，且位于(i,k)最短路径上的边的价值和cnt[i][k]，这个预处理需要枚举i,k并检查以k为以端点的边的另一端点是否在(i,k)的最短路上，复杂度O(n^3)

这样ans[i][j]=\sum\limits_kcnt[i][k] (k位于(i,j)最短路上)，这样对于每个点对只需要枚举O(n)个点，总时间复杂度O(n^3)

STD

#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
const int MAX=5e2+5;
const int inf=1061109567;
int n,m;
int len[MAX][MAX],value[MAX][MAX];
int dis[MAX][MAX],cnt[MAX][MAX];
inline void pre(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++)if(dis[i][k]!=-1 && dis[k][j]!=-1){
				if(dis[i][j]==-1 || dis[i][j]>dis[i][k]+dis[k][j])dis[i][j]=dis[i][k]+dis[k][j];
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int k=1;k<=n;k++)if(dis[i][k]!=-1){
			for(int j=1;j<=n;j++)if(j!=k && dis[i][j]!=-1 && len[j][k]!=-1 && dis[i][j]+len[j][k]==dis[i][k])cnt[i][k]+=value[j][k];
		}
	}
}
signed main(){
	scanf("%lld %lld",&n,&m);
	memset(dis,-1,sizeof(dis));
	for(int x,y,i=1;i<=m;i++)scanf("%lld %lld",&x,&y),scanf("%lld %lld",&dis[x][y],&value[x][y]),dis[y][x]=dis[x][y],value[y][x]=value[x][y];
	for(int i=1;i<=n;i++)dis[i][i]=0;
	memcpy(len,dis,sizeof(dis));
	pre();
	for(int i=1;i<=n;i++){
		for(int ans,j=i+1;j<=n;j++){
			ans=0;
			for(int k=1;k<=n;k++)if(dis[i][k]+dis[k][j]==dis[i][j])ans+=cnt[i][k];
			printf("%lld ",ans);
		}
	}
	return 0;
}