LA 4080 战争和物流（最短路树）

题意：
给出一个n个结点m条边的无向图，每条边上有一个正权。令c等于每对结点的最短路长度之和。不连通的两点的最短路长度视为L。

求出初始时的最短路长度之和以及删除一条边后最大的最短路长度之和。

思路：

最短路树其实很简单，就是用一个二维数组记录某个源点出发所经过的边，如$belong[s][i]$就说明源点s出发经过了i这条边。这样做的好处是当我们枚举删除的边的时候，如果它不在当前源点的最短路树上，那么对于最短路不会有影响，如果在，那么此时就要重新跑最短路。这样可以节约很多时间。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<vector>
  6 #include<stack>
  7 #include<queue>
  8 #include<cmath>
  9 #include<map>
 10 #include<set>
 11 #include<bitset>
 12 using namespace std;
 13 typedef long long ll;
 14 typedef pair<int,int> pll;
 15 const ll INF = (ll)1<<30;
 16 const int maxn=100+5;
 17 
 18 int n,m,tot,l;
 19 ll ans;
 20 int head[maxn];
 21 bool vis[maxn],del[2005],belong[maxn][2005];
 22 ll d[maxn],w[maxn];
 23 int p[maxn];
 24 
 25 struct node
 26 {
 27     int id,v,d,next;
 28 }e[maxn*maxn];
 29 
 30 struct HeapNode
 31 {
 32     int u; ll d;
 33     HeapNode(int u, ll d):u(u),d(d){}
 34     bool operator<(const HeapNode& rhs) const
 35     {
 36         return d>rhs.d;
 37     }
 38 };
 39 
 40 void addEdge(int id, int u, int v, int d)
 41 {
 42     e[tot].id=id;
 43     e[tot].d=d;
 44     e[tot].v=v;
 45     e[tot].next=head[u];
 46     head[u]=tot++;
 47 }
 48 
 49 void dijkstra1(int s)
 50 {
 51     priority_queue<HeapNode> Q;
 52     memset(vis,false,sizeof(vis));
 53     for(int i=1;i<=n;i++)  d[i]=INF;
 54     d[s]=0;
 55     Q.push(HeapNode(s,0));
 56     while(!Q.empty())
 57     {
 58         HeapNode x=Q.top(); Q.pop();
 59         int u=x.u;
 60         if(vis[u])  continue;
 61         belong[s][p[u]]=true;
 62         vis[u]=true;
 63         for(int i=head[u];i!=-1;i=e[i].next)
 64         {
 65             int v=e[i].v;
 66             if(d[v]>d[u]+e[i].d)
 67             {
 68                 d[v]=d[u]+e[i].d;
 69                 p[v]=e[i].id;
 70                 Q.push(HeapNode(v,d[v]));
 71             }
 72         }
 73     }
 74     for(int i=1;i<=n;i++)
 75     {
 76         if(d[i]==INF)
 77         {
 78             w[s]+=l;
 79             ans+=l;
 80         }
 81         else
 82         {
 83             w[s]+=d[i];
 84             ans+=d[i];
 85         }
 86     }
 87 }
 88 
 89 ll dijkstra2(int s)
 90 {
 91     priority_queue<HeapNode> Q;
 92     memset(vis,false,sizeof(vis));
 93     for(int i=1;i<=n;i++)  d[i]=INF;
 94     d[s]=0;
 95     Q.push(HeapNode(s,0));
 96     while(!Q.empty())
 97     {
 98         HeapNode x=Q.top(); Q.pop();
 99         int u=x.u;
100         if(vis[u])  continue;
101         vis[u]=true;
102         for(int i=head[u];i!=-1;i=e[i].next)
103         {
104             int v=e[i].v;
105             if(del[e[i].id])  continue;
106             if(d[v]>d[u]+e[i].d)
107             {
108                 d[v]=d[u]+e[i].d;
109                 Q.push(HeapNode(v,d[v]));
110             }
111         }
112     }
113     ll tmp=0;
114     for(int i=1;i<=n;i++)
115     {
116         if(d[i]==INF) tmp+=l;
117         else tmp+=d[i];
118     }
119     return tmp;
120 }
121 
122 int main()
123 {
124     //freopen("in.txt","r",stdin);
125     while(~scanf("%d%d%d",&n,&m,&l))
126     {
127         tot=0;
128         memset(head,-1,sizeof(head));
129         memset(del,false,sizeof(del));
130         memset(belong,false,sizeof(belong));
131         memset(w,0,sizeof(w));
132         for(int i=1;i<=m;i++)
133         {
134             int u,v,w;
135             scanf("%d%d%d",&u,&v,&w);
136             addEdge(i,u,v,w);
137             addEdge(i,v,u,w);
138         }
139         ans=0;
140         for(int i=1;i<=n;i++)  dijkstra1(i);
141         printf("%lld ",ans);
142         ans=0;
143         for(int i=1;i<=m;i++)
144         {
145             ll tmp=0;
146             del[i]=true;
147             for(int j=1;j<=n;j++)
148             {
149                 if(belong[j][i])  tmp+=dijkstra2(j);
150                 else tmp+=w[j];
151             }
152             del[i]=false;
153             ans=max(ans,tmp);
154         }
155         printf("%lld
",ans);
156     }
157     return 0;
158 }