http://acm.hdu.edu.cn/showproblem.php?pid=1595
第一次写spfa 一路下来都蛮流畅的 而且1a 哇哈哈 纪念一下 ^ _ ^
题意 N个点 M条边 其中有一条未知边无法通过 找出第I条边无法通过时的最短路中的最大者（1<=i<=m）
思路： 先找出所有便可以通过时的最短路 记录下最短路的路径 再找出该路径中的某一条边无法通过时从 1--->n 的最短路 （若无法通过的边不在最短路的路径中那 那条边最短路也不会变啦） 比较得到最大者 就是答案了
代码如下
#include<iostream> #include<vector> #include<string.h> #include<queue> using namespace std; #define INF 100000000 vector<int > g[1002]; int w[1002][1002],d[1002],vis[1002]; struct edge{int u;int v;}e[100000]; void spfa(int a,int n) { queue<int > q; memset(vis,0,sizeof(vis));//不在队列中 for(int i=2;i<=n;i++) d[i]=INF; d[1]=0; q.push(1); vis[1]=1; while(!q.empty()) { int a,b; a=q.front(); q.pop(); for(int i=0;i<g[a].size();i++) { b=g[a][i]; if(w[a][b]!=-1) { if(d[b]>d[a]+w[a][b]) { d[b]=d[a]+w[a][b]; if(vis[b]==0) q.push(b); } } } } } int main() { int i,j,n,m,a,b,c; while(scanf("%d%d",&n,&m)!=EOF) { memset(w,-1,sizeof(w)); for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); w[a][b]=c; w[b][a]=c; if(c>w[a][b]&&w[a][b]!=-1) continue; g[a].push_back(b); g[b].push_back(a); } spfa(1,n);// 得到 全部能通过时的最短路 //printf("ans %d ",d[n]); int u=n; int num=0; while(u!=1) { for(i=0;i<g[u].size ();i++) { int v=g[u][i]; if(d[v]+w[u][v]==d[u]) { edge temp; temp.u =u; temp.v=v; e[num++]=temp;u=v; // 记录最短路的路径 break; } } } int maxx=0; for(i=0;i<num;i++) //一个个来 找最短路径中的某一条边 去掉后的最短路 { int temp; temp=w[e[i].u ][e[i].v ]; w[e[i].u ][e[i].v]=w[e[i].v ][e[i].u]=-1; spfa(1,n); if(d[n]>maxx) //比较得出 最大者 maxx=d[n]; w[e[i].u ][e[i].v]=w[e[i].v ][e[i].u]=temp; } printf("%d ",maxx); // for(i=0;i<num;i++) //ok // printf("edge %d %d ",e[i].u,e[i].v); for(i=1;i<=n;i++) g[i].clear(); } return 0; }