震惊，set 比 priority_queue 要慢

Problem

给出一个 N 节点 M 条边的无向图，每条边上有一个正权，令 c 等于每对结点的最短路径之和，要求删除一条边后使得新的 c 值最大，不连通的两个点距离视为 L。
translated by Awson

Solution

本题就卡卡常能过...
枚举删哪条边，然后跑 n 遍 dijkstra...
复杂度 $O(n^2m\log n)$，卡在 2.8s 过了...

事实上能优化一下...
只有改了每个点的最短路树上的边才会使最短路值更改...
于是复杂度就降到了 $O(n^3\log n)$...STL 不开 O2 0.7s.. 用玄学堆的话可能会更快些（雾）

注意边不能重复删啊会 TLE 的 qwq

最近做题好像总会 wa 上 n 遍 qwq

Code

// Code by ajcxsu
// Problem: warfare

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=110, M=2010;
int h[N], to[M], nexp[M], W[M], p=2;
bool del[M], tag[M];
inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }
int n, m;
ll L;

int dist[N], pre[N], mpre[N];
bool S[N];
typedef pair<int, int> mpair;
ll dijkstra(int s) {
    memset(dist, 0x3f, sizeof(dist)), memset(S, 0, sizeof(S)), memset(pre, 0, sizeof(pre));
    ll ret=0;
    priority_queue<mpair, vector<mpair>, greater<mpair> > pq;
    dist[s]=0;
    pq.push(mpair(0, s));
    int u;
    for(int i=1;i<=n;i++) {
        while(!pq.empty() && (S[pq.top().second] || dist[pq.top().second]<pq.top().first)) pq.pop();
        if(pq.empty()) break;
        u=pq.top().second, pq.pop();
        S[u]=1;
        ret+=dist[u];
        for(int uu=h[u];uu;uu=nexp[uu])
            if(!del[uu] && !S[to[uu]] && dist[to[uu]]>dist[u]+W[uu])
                dist[to[uu]]=dist[u]+W[uu], pre[to[uu]]=uu, pq.push(mpair(dist[to[uu]], to[uu]));
    }
    for(int i=1;i<=n;i++) if(dist[i]==0x3f3f3f3f) ret+=L;
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    while(cin>>n>>m>>L) {
        p=2, memset(h, 0, sizeof(h)), memset(tag, 0, sizeof(tag));
        int u, v, w;
        for(int i=1;i<=m;i++) {
            cin>>u>>v>>w;
            ins(u, v, w), ins(v, u, w);
        }
        ll ans1=0, ans2=0, sum;
        for(int i=1;i<=n;i++) {
            ans1+=dijkstra(i);
            memcpy(mpre, pre, sizeof(pre));
            for(int j=1;j<=n;j++)
                if(mpre[j] && !tag[mpre[j]]) {
                    del[mpre[j]]=del[mpre[j]^1]=1, sum=0;
                    tag[mpre[j]]=tag[mpre[j]^1]=1;
                    for(int k=1;k<=n;k++) sum+=dijkstra(k);
                    ans2=max(ans2, sum);
                    del[mpre[j]]=del[mpre[j]^1]=0;
                }
        }
        cout<<ans1<<' '<<ans2<<endl;
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-uva-1416.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆