题意：给你N个点和m条边的无向图，然后让你求出依次删除2-n-1号的点之后的到达N点最短路的最大值，如果删除某个点之后，不能到达N点，就输出Inf，。
思路：枚举删除的点，然后SPFA就可以求最短路，然后求出最大值就可以。
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <algorithm> 5 using namespace std; 6 const int inf=1<<20; 7 8 int n,m; 9 int g[40][40]; 10 bool vis[40]; 11 int dis[40]; 12 bool vis1[40]; 13 int cnt[1000]; 14 15 16 void spfa(int src,int x) 17 { 18 memset(cnt,0,sizeof(cnt)); 19 memset(vis1,false,sizeof(vis1)); 20 for(int i=1; i<=n; i++) dis[i]=inf; 21 dis[src]=0; 22 vis1[src]=true; 23 queue<int>q; 24 q.push(src); 25 while(!q.empty()) 26 { 27 int u=q.front(); 28 q.pop(); 29 vis1[u]=false; 30 for(int i=1; i<=n; i++) 31 { 32 if(g[u][i]&&i!=x) 33 { 34 if(dis[i]>dis[u]+g[u][i]) 35 { 36 dis[i]=dis[u]+g[u][i]; 37 if(!vis1[i]) 38 { 39 q.push(i); 40 vis1[i]=true; 41 } 42 } 43 } 44 } 45 } 46 } 47 int main() 48 { 49 while(scanf("%d%d",&n,&m)!=EOF) 50 { 51 if(n==0&&m==0) break; 52 memset(g,0,sizeof(g)); 53 for(int i=1; i<=m; i++) 54 { 55 int a,b,c; 56 scanf("%d%d%d",&a,&b,&c); 57 g[a][b]=g[b][a]=c; 58 } 59 int ans=0; 60 bool flag=false; 61 for(int i=2; i<n; i++) 62 { 63 spfa(1,i); 64 if(dis[n]==inf) flag=true; 65 ans=max(ans,dis[n]); 66 } 67 if(flag) printf("Inf "); 68 else 69 printf("%d ",ans); 70 } 71 return 0; 72 }