HDU1595-find the longest of the shortest-dijkstra+记录路径

  1 #include<iostream>
  2 #include<string.h>
  3 #include<cmath>
  4 #include<iomanip>
  5 #define inf 0x3f3f3f3f
  6 #define ios() std::ios::sync_with_stdio(false)
  7 #define cin() cin.tie(0)
  8 #define cout() cout.tie(0)
  9 #define mem(a) memset(a,0,sizeof(a))
 10 using namespace std;
 11 
 12 int vertex[1001];//记录首先求得的最短路径所经过的顶点
 13 int n,m;//n顶点总个数，m是边数
 14 int e[1001][1001];
 15 int dis[1001],dis1[1001],dis2[1001];
 16 int book[1001];
 17 int flag;
 18 
 19 void init()
 20 {
 21     for(int i=1; i<=n; i++)
 22     {
 23         for(int j=1; j<=n; j++)
 24         {
 25             if(i==j)
 26                 e[i][j]=0;
 27             else
 28                 e[i][j]=inf;
 29             }
 30     }
 31 }
 32 
 33 int  dijkstra(int *dis)
 34 {
 35     mem(book);mem(dis1);mem(dis2);
 36     for(int i=1;i<=n;i++)
 37         dis[i]=e[1][i];
 38     book[1]=1;
 39     int u;
 40     for(int i=2;i<=n;i++)
 41     {
 42         int minn=inf;
 43         for(int j=1;j<=n;j++)
 44         {
 45             if(book[j]==0&&dis[j]<minn)
 46             {
 47                 u=j;
 48                 minn=dis[j];
 49             }
 50         }
 51         book[u]=1;
 52         for(int k=1;k<=n;k++)
 53         {
 54             if(e[u][k]<inf&&dis[u]+e[u][k]<dis[k])
 55             {
 56                 dis[k]=dis[u]+e[u][k];
 57                 if(flag)//如果flag=1，则开始记录最短路的路径
 58                 {
 59                     vertex[k]=u;//记录顶点
 60                 }
 61             }
 62         }
 63     }
 64     return dis[n];
 65 }
 66 
 67 int main()
 68 {
 69     ios();cin();cout();
 70     int x,y,z;
 71     while(cin>>n>>m)
 72     {
 73         mem(dis);mem(vertex);mem(e);
 74         init();
 75         for(int i=0; i<m; i++)
 76         {
 77             cin>>x>>y>>z;
 78             e[x][y]=z;
 79             e[y][x]=z;
 80         }
 81 
 82         flag=1;mem(dis1);
 83         fill(vertex,vertex+1001,1);
 84         int shortest=dijkstra(dis1);
 85       //  cout<<shortest<<"**"<<endl;
 86 
 87 //        for(int i=n;i>=2;i--)
 88 //            cout<<vertex[i]<<" ";
 89 
 90         flag=0;//通过控制flag决定是否记录路径
 91         int w=n;//一步步倒回去替换掉每一段的距离且变成无穷大，寻找其他边
 92         int ans=shortest;
 93         while(w!=1)//   通过while去控制是否已经倒退回去遍历到所有的边
 94         {
 95           //  cout<<"***"<<endl;
 96             int frontt=vertex[w];
 97             int ori=e[frontt][w];
 98             e[frontt][w]=e[w][frontt]=inf;//第一次进去先变最后一条边
 99             mem(dis2);
100             int ww=dijkstra(dis2);
101           //  if(ww!=inf)
102                 ans=max(ww,ans);
103             e[frontt][w]=e[w][frontt]=ori;
104             w=frontt;
105            // 变成无穷大之后再进行下一次找的时候可能会需要到这条边，所以需要恢复
106         }
107         cout<<ans<<endl;
108     }
109     return 0;
110 }