【Dijstra堆优化】HDU 3986 Harry Potter and the Final Battle

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

http://acm.hdu.edu.cn/showproblem.php?pid=3986

【题意】

给定一个有重边的无向图，T=20,n<=1000,m<=5000
删去一条边，使得1~n的最短路最长
求最短路最长是多少

【思路】

一定是删最短路上的边
可以先跑一个Dijkstra,求出最短路，然n后枚举删边
朴素的Dijkstra为n^2,枚举删边(n条)需要的总时间复杂度是n^3
堆优化Dijkstra（nlogn），总复杂度为n^2logn
有多重边，用邻接矩阵不方便，用邻接表方便，删去的边标记一下就好

【Accepted】

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<string>

 #include<algorithm>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 const int maxm=5e4*+;

 const int maxn=1e3+;

 const int inf=0x3f3f3f3f;

 int n,m;

 struct node

 {

     int to;

     int nxt;

     int w;

 }e[maxm];

 int head[maxn];

 int tot;

 bool vis[maxn];

 int dis[maxn];

 int pv[maxn];

 int pe[maxn];

 typedef pair<int,int> pii;

 void init()

 {

     memset(head,-,sizeof(head));

     tot=;

 }

 void add(int u,int v,int w)

 {

     e[tot].to=v;

     e[tot].w=w;

     e[tot].nxt=head[u];

     head[u]=tot++;

 }

 int Dij(int x)

 {

     priority_queue<pii,vector<pii>,greater<pii> >pq;

     memset(vis,false,sizeof(vis));

     memset(dis,inf,sizeof(dis));

     dis[]=;

     pq.push(make_pair(dis[],));

 //    pq.push(pii(dis[1],1));

     while(!pq.empty())

     {

         pii cur=pq.top();

         pq.pop();

         int u=cur.second;

         if(vis[u]) continue;

         vis[u]=true;

         for(int i=head[u];i!=-;i=e[i].nxt)

         {

             if(i==x) continue;

             int w=e[i].w;

             int v=e[i].to;

             if(dis[u]+w<dis[v])

             {

                 dis[v]=dis[u]+w;

                 pq.push(make_pair(dis[v],v));

                 if(x==-)

                 {

                     pv[v]=u;

                     pe[v]=i;

                 }

             }

         }

     }

     return dis[n];

 }

 int Solve()

 {

     if(Dij(-)==inf)

     {

         return -;

     }

     int ans=;

     for(int i=n;i!=;i=pv[i])

     {

         ans=max(ans,Dij(pe[i]));

         if(ans==inf)

         {

             return -;

         }

     }

     return ans;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         init();

         scanf("%d%d",&n,&m);

         while(m--)

         {

             int u,v,w;

             scanf("%d%d%d",&u,&v,&w);

             add(u,v,w);

             add(v,u,w);

         }

         int ans=Solve();

         printf("%d\n",ans);

     }

     return ;

 }