[蓝书][图论][最短路][坑] UVALive 4080 Walfare And Logistics

题目链接 https://cn.vjudge.net/problem/UVALive-4080

最短路基础题，有意思的部分在于最短路树这个东西的应用，还有对复杂度的正确估算（莽

看题目意思，基本上能确定枚举那条要去除的边然后算每种情况的c，但是如果直接这样的话复杂度会是n*m²*logn,就题目数据量而言基本上不可能过的。所以就要找其他方法来降低复杂度，考虑到，去掉一条边也许不会对以某些点为原点的到每个点的单源最短路产生影响（也就是不在这些点的最短路树上的边），可以试着预处理出来初始状态下每个边的影响到的点的集合，在枚举到这条边的时候只需要重新计算这些点的最短路而不用每次都计算所有点的最短路，这样的话可以把复杂度降低到n²mlogn。不得不吐槽一下这个解法，说实话感觉并没有降低多少就卡过了时限，数据刻意友好么。。。。比赛的话就算能想到这个也不一定敢写吧emmm

坑点是有重边，果然做图论最重要的是搞清楚图的类型。。。重边啊自环啊什么的真的烦,还有一开始小根堆写成大根堆了，又是wa又是t的

 

#include <iostream>
#include <cstring>
#include <string>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<set>
#include<vector>

using namespace std;
typedef long long LL;
const int maxn=100+5;
const int mod =1e9+7;
const int inf =0x3f3f3f3f;

struct edge
{
    int to,w,id;
    edge()
    {
        to=w=id=0;
    }
    edge(int to,int w,int id):to(to),w(w),id(id) {}
};

struct node
{
    int d,id;
    node()
    {
        d=id=0;
    }
    node(int d,int id):d(d),id(id) {}
    bool operator<(const struct node & rhs)const
    {
        return d>rhs.d;
    }
};

vector<edge> G[maxn];
int banid;
int g[maxn][maxn];
vector<int > infect[maxn][maxn];
int dis[maxn];
LL DD[maxn];
int n,m,L;
int pa[maxn];

LL sssp(int s)
{

    memset(dis,inf,sizeof(dis));
    dis[s]=0;
    priority_queue<node> Q;
    Q.push(node(0,s));
    node cur;
    int x,len,v,c;
    while(!Q.empty())
    {
        cur=Q.top();
        Q.pop();
        if(cur.d!=dis[cur.id])
            continue;
        x=cur.id;
        len=G[x].size();
        for (int i=0; i<len; i++)
            if(g[x][G[x][i].to]>0||g[x][G[x][i].to]==-1&&G[x][i].id!=banid)
            {
                v=G[x][i].to,c=G[x][i].w;
                if(dis[v]>dis[x]+c)
                {
                    dis[v]=dis[x]+c;
                    Q.push(node(dis[v],v));

                }
            }
    }
    LL res=0;
    for (int i=1; i<=n; i++)
    {
        res+=(dis[i]==inf?L:dis[i]);
        //dis[i]=inf;
    }
    return res;
}

LL presssp(int s)
{
    memset(pa,0,sizeof(pa));
    memset(dis,inf,sizeof(dis));
    dis[s]=0;
    priority_queue<node> Q;
    Q.push(node(0,s));
    node cur;
    int x,len,v,c;
    while(!Q.empty())
    {
        cur=Q.top();
        Q.pop();
        if(cur.d!=dis[cur.id])
            continue;
        x=cur.id;
        len=G[x].size();
        for (int i=0; i<len; i++)
            if(g[x][G[x][i].to])
            {
                v=G[x][i].to,c=G[x][i].w;
                if(dis[v]>dis[x]+c)
                {
                    dis[v]=dis[x]+c;
                    Q.push(node(dis[v],v));
                    pa[v]=x;
                }
            }
    }
    LL res=0;
    for (int i=1; i<=n; i++)
    {
        res+=(dis[i]==inf?L:dis[i]);
    }


    for(int i=1; i<=n; i++)
    {
        if(pa[i])
        {
            infect[pa[i]][i].push_back(s);
            infect[i][pa[i]].push_back(s);
        }
    }
    DD[s]=res;
    return res;
}

LL check(int u,int v)
{
    LL res=0;
    int len=infect[u][v].size();
    for(int i=0; i<len; i++)
    {
        res+=sssp(infect[u][v][i])-DD[infect[u][v][i]];
    }
    return res;
}

void init()
{
    memset(DD,0,sizeof(DD));
    memset(pa,0,sizeof(pa));
    memset(g,0,sizeof(g));
    memset(dis,inf,sizeof(dis));
    for (int i=1; i<=n; i++)
        G[i].clear();
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            infect[i][j].clear();
}

int main()
{
    //freopen("palindrome.in", "r", stdin);
    //freopen("palindrome.out", "w", stdout);
    int a,b,s,v;
    while(scanf("%d%d%d",&n,&m,&L)==3)
    {
        init();
        for (int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&a,&b,&s);
            g[a][b]++,g[b][a]++;
            G[a].push_back(edge(b,s,g[a][b]));
            G[b].push_back(edge(a,s,g[a][b]));
        }
        edge tmp;
        LL ans=0,cc=0;
        for (int i=1; i<=n; i++)
        {
            cc+=presssp(i);
        }
        memset(dis,inf,sizeof(dis));
        int fuck;
        for (int i=1; i<=n; i++)
        {
            int len=G[i].size();
            for (int j=0; j<len; j++)
            {
                tmp=G[i][j];
                v=tmp.to;
                fuck=g[i][v];
                if(g[i][v]>1)
                {
                    g[i][v]=g[v][i]=-1;
                    banid=tmp.id;
                }
                else
                    g[i][v]=g[v][i]=false;
                ans=max(ans,cc+check(i,v));
                g[i][v]=g[v][i]=fuck;
            }
        }
        cout<<cc<<" "<<ans<<"\n";
    }
    return 0;
}