题目链接：http://acm.fzu.edu.cn/problem.php?pid=2271
题目中说每条边的边权都是[1,10]之间的整数，这个条件非常关键！以后一定要好好读题啊……
做10次循环，第i次循环加边权为i的边，如果这条边小于当前两点间最短路，就加边，更新两点距离；否则就不要这个边。
每次循环过后，做一次Floyd。至多做10次Floyd。
有一个猜想，比赛的时候就想到了：从小到大加边，如果这个边比这两点之间的最短距离小，就要，否则就不要。这个猜想不会证……
但是只想到了每次更改距离以后都做一次Floyd，没有想到一块加权值相同的边，然后再做Floyd。这里就假设上面的猜想是正确的，然后证明一下统一做Floyd的方法也是正确的吧。
假设dis[][]维护着两点间的最短距离。
首先，对于未经优化的方法，如果有一条边加入了，说明这条边的权比两点的最短路短，如果没有随时维护，只维护到了上次权值不同的最后一条边，由于dis随着维护是越来越小的，所以现在的dis也显然大于这个边权，因此对于没有优化的方法，这条边会加进去。
然后，对于未经优化的方法，如果有一条边没有加入，说明这条边的权w不比两点的最短路短，如果没有随时维护，只维护到了上次权值不同的最后一条边，由于用[1,w-1]的边构成的最短路已经得到，假设这条权值是w的边在优化后会加入，也就是说当前的dis>w，而优化以前没有加入，说明dis'<=w，所以意思就是，加入了一些权值为w的边以后，dis变得<=w了，那这个dis'只能是=w了。既然是权值为w的最短路，要么是用权值为w的边得到的，那此时dis应该也=w了，因为每遇到一个w的边都会更新距离。要么是用[1,w-1]的边构成的，那这个在[1,w-1]之后就应该已经维护出来了。这两种情况都与dis>w矛盾。所以假设失败，这条边在优化以后还是不会加入。
所以加不加入在优化前后是一样的。
#include<cstdio> #include<cstring> const int maxn=105; const int maxm=40005; const int INF=0x3f3f3f3f; struct Edge { int u,v,w; }edge[maxm]; int dis[maxn][maxn]; int main() { int t; scanf("%d",&t); for (int cas=1;cas<=t;cas++) { int n,m; scanf("%d%d",&n,&m); for (int i=0;i<m;i++) { scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); } memset(dis,INF,sizeof(dis)); for (int i=1;i<=n;i++) dis[i][i]=0; int ans=0; for (int z=1;z<=10;z++) { for (int e=0;e<m;e++) { if (edge[e].w==z) { int u=edge[e].u; int v=edge[e].v; if (z<dis[u][v]) { dis[u][v]=z; dis[v][u]=z; ans++; } } } 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]+dis[k][j]<dis[i][j]) dis[i][j]=dis[i][k]+dis[k][j]; } printf("Case %d: %d ",cas,m-ans); } return 0; }
另外还有一种更神的做法，只需要做一次Floyd。
首先，删掉重边和自环。然后剩下的边做一次Floyd，在做的过程中被松弛过的边都可以删去。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=405; const int INF=0x3f3f3f3f; int G[maxn][maxn]; int dis[maxn][maxn]; bool vis[maxn][maxn]; int main() { int t; scanf("%d",&t); for (int cas=1;cas<=t;cas++) { memset(G,INF,sizeof(G)); memset(dis,INF,sizeof(dis)); memset(vis,false,sizeof(vis)); int n,m; scanf("%d%d",&n,&m); int ans=0; for (int i=0;i<m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); if (G[u][v]<INF||u==v) ans++; if (w<G[u][v]&&u!=v) G[u][v]=G[v][u]=w; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) dis[i][j]=G[i][j]; 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]+dis[k][j]<=dis[i][j]) { dis[i][j]=dis[i][k]+dis[k][j]; vis[i][j]=true; } } for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) { if (vis[i][j]&&G[i][j]!=INF) ans++; } printf("Case %d: %d ",cas,ans); } return 0; }