开始的时候想的比较简单,直接枚举所有输入的边,但最后超时;后来就先进行一次dij,记录所有最短路上的边,然后枚举删去这些边;
#include<stdio.h> #include<string.h> #define maxn 1002 #define INF 99999999 int map[maxn][maxn],vis[maxn],n,dis[maxn]; int pre[maxn],flag; void init() { int i,j; for(i=0;i<=n;i++) for(j=0;j<=n;j++) if(i==j)map[i][j]=0; else map[i][j]=INF; } void dij() { int i,j,pos; pos=1; memset(vis,0,sizeof(vis)); for(i=0;i<=n;i++) dis[i]=INF; dis[pos]=0; vis[pos]=1; for(i=1;i<n;i++) { int min=INF; for(j=1;j<=n;j++) { if(!vis[j]&&min>dis[j]) { pos=j; min=dis[j]; } } vis[pos]=1; for(j=1;j<=n;j++) { if(dis[j]>dis[pos]+map[pos][j]) { if(!flag) pre[j]=pos; dis[j]=dis[pos]+map[pos][j]; } } } } int main() { int i,j,m; while(scanf("%d%d",&n,&m)!=EOF) { init(); memset(pre,-1,sizeof(pre)); for(i=0;i<m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); if(map[x][y]>z) map[x][y]=map[y][x]=z; } flag=0; dij(); flag=1; int max = dis[n]; for(i=n;i!=-1;i=pre[i]) { int t=map[pre[i]][i]; map[pre[i]][i]=map[i][pre[i]]=INF; dij(); if(dis[n]>max) max=dis[n]; map[pre[i]][i]=map[i][pre[i]]=t; } printf("%d ",max); } }