题意：

给出一个无向图，定义这个无向图的花费是

其中path(i,j)，是i到j的最短路。

去掉其中一条边之后，花费为c’，问c’ – c的最大值，输出c和c’。

思路：

枚举每条边，每次把这条边去掉，然后以每个点为起点，跑一次Dijkstra，再计算总花费。

这样的复杂度为O(mn^2log(n))，这个复杂度刚好卡着时间过，所以是暴力，更优的方法是最短路树（待学习。

代码：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 using namespace std;  6   7 struct edge  8 {  9     int to,cost; 10     int id; 11      12     edge(int uu,int vv,int idd) 13     { 14         to = uu; 15         cost = vv; 16         id = idd; 17     } 18 }; 19  20 const int maxn = 105; 21  22 typedef pair
         
           pii; 23 long long d[maxn]; 24 vector
          
            g[maxn]; 25 bool ma[1005]; 26 27 void adde(int st,int en,int cost,int id) 28 { 29 g[st].push_back(edge(en,cost,id)); 30 } 31 32 void dij(int s,int n) 33 { 34 for (int i = 0;i <= n;i++) d[i] = 1e16; 35 36 priority_queue
           
            
             ,greater
             
               > pq; 37 38 pq.push(pii(0,s)); 39 40 d[s] = 0; 41 42 //printf("***\n"); 43 44 while (!pq.empty()) 45 { 46 pii x = pq.top();pq.pop(); 47 48 int v = x.second; 49 50 if (d[v] < x.first) continue; 51 52 for (int i = 0;i < g[v].size();i++) 53 { 54 edge e = g[v][i]; 55 56 if (d[e.to] > d[v] + e.cost) 57 { 58 d[e.to] = d[v] + e.cost; 59 pq.push(pii(d[e.to],e.to)); 60 } 61 } 62 } 63 64 //printf("***\n"); 65 } 66 67 void dijk(int s,int n) 68 { 69 for (int i = 0;i <= n;i++) d[i] = 1e16; 70 71 priority_queue
              
               
                ,greater
                
                  > pq; 72 73 pq.push(pii(0,s)); 74 75 d[s] = 0; 76 77 while (!pq.empty()) 78 { 79 pii x = pq.top();pq.pop(); 80 81 int v = x.second; 82 83 if (d[v] < x.first) continue; 84 85 for (int i = 0;i < g[v].size();i++) 86 { 87 edge e = g[v][i]; 88 89 if (ma[e.id]) continue; 90 91 if (d[e.to] > d[v] + e.cost) 92 { 93 d[e.to] = d[v] + e.cost; 94 pq.push(pii(d[e.to],e.to)); 95 } 96 } 97 } 98 99 //printf("***\n");100 }101 102 int main()103 {104 int n,m,l;105 106 while (scanf("%d%d%d",&n,&m,&l) != EOF)107 {108 for (int i = 0;i <= n;i++) g[i].clear();109 110 for (int i = 0;i < m;i++)111 {112 int a,b,c;113 114 scanf("%d%d%d",&a,&b,&c);115 116 adde(a,b,c,i);117 adde(b,a,c,i);118 }119 120 long long ans = 0;121 122 for (int i = 1;i <= n;i++)123 {124 125 126 dij(i,n);127 128 for (int j = 1;j <= n;j++)129 {130 if (d[j] == 1e16) d[j] = l;131 ans += d[j];132 }133 }134 135 136 137 long long res = 0;138 long long tmp = 0;139 140 for (int i = 0;i < m;i++)141 {142 ma[i] = 1;143 144 long long orz = 0;145 146 for (int j = 1;j <= n;j++)147 {148 dijk(j,n);149 150 for (int k = 1;k <= n;k++)151 {152 if (d[k] == 1e16) d[k] = l;153 orz += d[k];154 }155 }156 157 if (orz - ans > tmp)158 {159 res = orz;160 tmp = orz - ans;161 }162 163 ma[i] = 0;164 }165 166 printf("%lld %lld\n",ans,res);167 }168 169 return 0;170 }