题目链接：
题目大意：①先求任意两点间的最短路径累加和，其中不连通的边权为L ②删除任意一条边,求全局最短路径和的最大值。
解题思路：
首先说下多源最短路中，floyd和和优先队列优化的dijkstra的取舍。floyd比较好拍，dijkstra具有常数有势，以及灵活性（如求第二问的时候）。
本题最烦人的是枚举删除一条边，按照正常思维，要重新做n次dijkstra，复杂度已经到了可怕的(n*m^2*logn),那么是否有必要每次修改一条边的时候，全源重新做一次最短路呢？
答案是否定的。只要构建一颗最短路径树即可。
不要被名字唬住，其实就是一个二维数组，belong[边id][s点]，即初次做全源Dijkstra的时候，为每条边进行标记，标记内容为本次dij的s点。
注意这里的边指的是输入边id，不是图中的边（这题是无向图，输入边被add了两次）。
枚举删除边时，如果belong[边id][s点]=true,则说明这条边与这次的单源dij有关，必须重新dij。如果为false，则无关，值还是初次做dij的值。
标记belong的方法：在每次优先队列出队的时候，对出队点所在的入队前的边进行标记，具体方法是开一个p数组，每次Relax的时候，记录一下Relax的边即可。之后入队在取出，p数组就能立刻取出入队前的边了。
本题存在重边，不支持的重边的数据结构注意了，尤其是邻接表。推荐链式前向星。
另外两个问的结果都超过了int32。
#include "cstdio"#include "queue"#include "cstring"using namespace std;#define maxn 155#define maxp 2005#define inf 1<<28#define LL long longstruct Edge{ int next,to,d,id;}e[maxp*2];struct status{ int d,p; status(int d,int p):d(d),p(p) {} bool operator < (const status &a) const { return d > a.d;}};int n,m,l,tol,head[maxn],d[maxn],p[maxn],dis[maxn][maxn];LL ans1,ans2,w[maxn];bool vis[maxn],belong[maxp][maxn],del[maxp];void addedge(int u,int v,int c,int id){ e[tol].id=id; e[tol].d=c; e[tol].to=v; e[tol].next=head[u]; head[u]=tol++;}void dijkstra1(int s){ memset(vis,false,sizeof(vis)); memset(p,0,sizeof(p)); for(int i=1;i<=n;i++) d[i]=(i==s?0:inf); priority_queue Q; Q.push(status(0,s)); while(!Q.empty()) { status tt=Q.top();Q.pop(); int x=tt.p; if(vis[x]) continue; vis[x]=true; belong[p[x]][s]=true; for(int i=head[x];i!=-1;i=e[i].next) { int v=e[i].to; if(d[x]+e[i].d Q; Q.push(status(0,s)); while(!Q.empty()) { status tt=Q.top(); Q.pop(); int x=tt.p; if(vis[x]) continue; vis[x]=true; for(int i=head[x]; i!=-1; i=e[i].next) { if(del[e[i].id]) continue; //标记为删除的边跳过 int v=e[i].to; if(d[x]+e[i].d
| 2814660 | Accepted | 0 KB | 409 ms | 2990 B | 2014-10-04 18:34:44 |