输入格式: 输入说明：输入第1行给出两个正整数N和M，其中N是考试涉及的动物总数，M是用于直接变形的魔咒条数。为简单起见，我们将动物按1~N编号。随后M行，每行给出了3个正整数，分别是两种动物的编号、以及它们之间变形需要的魔咒的长度 输出格式: 输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出0。如果有若干只动物都可以备选，则输出编号最小的那只。
#include <cstdio> #include <cstring> #include <map> #include <string> #include <vector> #include <cmath> #include <iostream> #include <algorithm> using namespace std; const int INF=0x3f3f3f3f,N=105; int dis[N],w[N][N],vis[N]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) w[i][j]=0; else w[i][j]=INF; for(int i=0;i<m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(w[a][b]>c) w[a][b]=w[b][a]=c; } int ma=-1,p,mi,ani=INF,mmi=INF; for(int i=1;i<=n;i++) dis[i]=INF; for(int s=1;s<=n;s++) { for(int i=1;i<=n;i++) { vis[i]=0; dis[i]=w[s][i]; } vis[s]=1; dis[s]=0; while(1) { p=-1; mi=INF; for(int i=1;i<=n;i++) { if(mi>dis[i]&&!vis[i])//找寻最短的路程 { mi=dis[i]; p=i; } } if(p==-1) break; vis[p]=1; for(int i=1;i<=n;i++) if(dis[i]>(dis[p]+w[p][i])&&!vis[i]) dis[i]=dis[p]+w[p][i]; ma=-1; for(int i=1;i<=n;i++) if(ma<dis[i]) ma=dis[i]; if(mmi>ma)//当最短路中最长的魔咒长度（mmi）变化时，动物（ani）才变化 { ani=s; mmi=ma; } } } if(mmi!=INF) printf("%d %d\n",ani,mmi);// else printf("0\n");//当只带1只动物不可能完成所有变形要求 }