学步园

           题意:

                     给了一个无向图...问两两间最短距离之和为多少..当两点不可达时..那么令其距离为L...现在还能删去一条边..问所能得到的两两之和最大为多少...

           题解:

                    先做N次dijkstra..记录每个点位源点的djikstra中有哪些边...并且得到原始状态下两两间距离之和...

                    然后就是枚举删哪条边...枚举一条边...扫N个点..看这条边是否在某些记录中..如果有..则对于这些点重新做djikstra...更新答案即可..

                    恶心的是数据范围...开成105,2005..狂WA不止...开成155,2055才给过...还有注意的是Uva的64位整型用%lld读入读出..

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include <stack>
#include<queue>
#include<algorithm>
#include<cmath>
#define oo 1000000007
#define ll long long
#define pi acos(-1.0)
#define MAXN 155 
#define MAXM 2505
using namespace std;    
struct node
{
      int u,v,id,next;
      ll c; 
}edge[MAXM]; 
struct NODE
{
      int u,id;
      ll c;
      bool operator <(NODE a) const
      {
              return a.c<c;
      }
};
int Ne,_next[MAXN];
ll dis[MAXN][MAXN],t_dis[MAXN][MAXN],L;
bool b[MAXN][MAXM],t_b[MAXN][MAXM],used[MAXN];
void addedge(int u,int v,int c,int id)
{
      edge[++Ne].next=_next[u],_next[u]=Ne,edge[Ne].id=id;
      edge[Ne].u=u,edge[Ne].v=v,edge[Ne].c=c;
}
priority_queue<NODE> Q;
void dijkstra(int s,int n,int fbt)
{ 
      NODE h,k;
      int u,v,i;
      while (!Q.empty()) Q.pop();
      memset(used,false,sizeof(used));
      memset(dis[s],-1,sizeof(dis[s]));
      memset(b[s],false,sizeof(b[s]));
      dis[s][s]=0,h.u=s,h.c=h.id=0,Q.push(h);
      while (!Q.empty())
      {
              while (Q.size() && used[Q.top().u]) Q.pop();
              if (!Q.size()) break;
              h=Q.top(),Q.pop();  
              used[h.u]=true,b[s][h.id]=true;
              for (i=_next[h.u];i;i=edge[i].next)
              if (edge[i].id!=fbt)
              {
                      v=edge[i].v;
                      if (dis[s][v]==-1 || dis[s][v]>h.c+edge[i].c)
                      {
                              dis[s][v]=h.c+edge[i].c;
                              k.u=v,k.c=dis[s][v],k.id=edge[i].id,Q.push(k);
                      }
              }
      }
      dis[s][0]=0;
      for (i=1;i<=n;i++)
         if (dis[s][i]==-1) dis[s][0]+=L;
                       else dis[s][0]+=dis[s][i];
                 
}
int main()
{     
      int n,m,i,j,t,u,v,s;
      ll c1,c2,t_c;   
      while (~scanf("%d%d%lld",&n,&m,&L))
      {
               Ne=0,memset(_next,0,sizeof(_next));
               for (i=1;i<=m;i++)
                   scanf("%d%d%d",&u,&v,&s),addedge(u,v,s,i),addedge(v,u,s,i); 
               for (i=1;i<=n;i++) dijkstra(i,n,0);
               c1=0;
               for (i=1;i<=n;i++) c1+=dis[i][0]; 
               memcpy(t_dis,dis,sizeof(dis));
               memcpy(t_b,b,sizeof(dis));  
               c2=0;
               for (t=1;t<=m;t++) 
               {             
                       memcpy(dis,t_dis,sizeof(dis));
                       memcpy(b,t_b,sizeof(dis));    
                       t_c=c1;    
                       for (u=1;u<=n;u++)
                         if (b[u][t]) 
                         {
                                t_c-=dis[u][0]; // dis[u][0]记录之和 
                                dijkstra(u,n,t);
                                t_c+=dis[u][0];
                         } 
                       c2=max(c2,t_c);             
               }
               printf("%lld %lld\n",c1,c2);
      }
      return 0;
}