题意：给定一个无向图，删除某些边有一定的代价，要求删掉使得最短路径减小，求最小代价。

分析：首先要spfa求出起点到各个点的最短距离。对于一条权值为w，起点为i，终点为j的边，设dis[k]为起点到k点的距离，若dis[j]=dis[i]+w，则将该边加入另一个图里，边的容量为删除这条边的代价，则从起点到终点的最大流即为答案。。

　　1、首先最短路径一定在最短路图上

　　2、如果起点和终点不联通，就不存在这样一条最短路径，所以最短路径一定会变大；

注意看范围。。wa17发

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;const ll INF=1e18;const int M=1e4+4;struct node{    ll u,v,nextt;    ll w;}g[M<<2],e[M<<2];ll s,t,tot1,tot2,cur[M],head1[M],head2[M],vis[M],deep[M];ll dis[M];void addedge1(ll u,ll v,ll w){    g[tot1].u=u;    g[tot1].v=v;    g[tot1].w=w;    g[tot1].nextt=head1[u];    head1[u]=tot1++;}void addedge2(ll u,ll v,ll w){    e[tot2].v=v;    e[tot2].w=w;    e[tot2].nextt=head2[u];    head2[u]=tot2++;    e[tot2].v=u;    e[tot2].w=0;    e[tot2].nextt=head2[v];    head2[v]=tot2++;    }void dij(){    for(int i=0;i<=t;i++)        dis[i]=INF;//    cout<<"!!"<
           

que; que.push(s); dis[s]=0; while(!que.empty()){ ll u=que.front(); que.pop(); vis[u]=0; for(ll i=head1[u];~i;i=g[i].nextt){ ll v=g[i].v; if(dis[v]>dis[u]+g[i].w){ dis[v]=dis[u]+g[i].w; if(!vis[v]){ vis[v]=1; que.push(v); } } } }}ll dd[M];bool bfs(){ memset(deep,0,sizeof(deep)); queue

que; que.push(s); deep[s]=1; while(!que.empty()){ int u=que.front(); que.pop(); for(int i=head2[u];i!=-1;i=e[i].nextt){ int v=e[i].v; if(e[i].w>0&&deep[v]==0){ deep[v]=deep[u]+1; if(v==t) return true; que.push(v); } } } return deep[t]==0?false:true;}ll dfs(ll u,ll fl){ if(u==t) return fl; ll ans=0,x=0; for(int i=cur[u];i!=-1;i=e[i].nextt){ ll v=e[i].v; if(e[i].w>0&&deep[v]==deep[u]+1){ x=dfs(v,min(e[i].w,fl-ans)); e[i].w-=x; e[i^1].w+=x; if(e[i].w) cur[u]=i; ans+=x; if(ans==fl) return ans; } } if(ans==0) deep[u]=0; return ans;}ll dinic(){ ll ans=0; while(bfs()){ for(int i=0;i<=t;i++) cur[i]=head2[i]; ans+=dfs(s,INF); } return ans;}int main(){ ll test; scanf("%lld",&test); while(test--){ ll n,m; tot1=tot2=0; scanf("%lld%lld",&n,&m); // cout<

<<"!!"<

<