题解 P1186 【玛丽卡】

· · 题解

暂时运行效率rank1，大概是因为没有信仰，以为O(n^3)过不了1000，所以写了个O(n^2 log_2n)。

容易发现这题是一张稠密图，所以用O(n^2)的dijkstra即可，所谓的堆优化其实是劣化。关于SPFA，虽然这里没有死，但是已经死了。

是某道题目的简化版：做法一样。

首先我们进行一次dijkstra，得到点1到点n的最短路径（如果有多条，随便找一条）。

显然，如果移除的不是这条路径上的边，贡献是不变的，现在考虑如果移除这条路径上的边。

那么对于另外的某一条路径，可以去update这条路径上的一些边

如果最短路径是A->B->...->C->D，存在一条路径A->B->E->C->D，那么在B->...->C这一段路径上的所有边如果去掉，还有那条路经，所以可以更新。

那么转化成一个简单的问题：区间取min，最后求所有值。

这个直接线段树区间取min（标记永久化），最后dfs一遍得到所有路径上删掉之后的max（还可以排序之后并查集维护）

注意这里的我们维护的对于1~n最短路径上的每条边，删掉它之后的1到n的最短距离。

来口胡一下证明，显然如果一条边跨越显然是对的，因为这条边一定可以正确地更新答案。

如果有超过一条边跨越，这条链与1到n最短路径的相连的点一定是直接走最短路径最优（不会劣），那么中间一定有一条边一定有路径1->这条路径->n，显然不重复。

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
typedef long long ll;
#define gc getchar
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
inline ll read(){
    register ll x=0,f=1;register char c=gc();
    for(;!isdigit(c);c=gc())if(c=='-')f=-1;
    for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
#define pc putchar
void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');}
void writeln(ll x){write(x);puts("");}
const int maxn = 1005;
bool vis[maxn];
int d1[maxn],dn[maxn],pre[maxn];
int n,m;
int a[maxn][maxn];
void dijkstra(int S,int dist[]){
    Rep(i,1,n) vis[i] = false;
    Rep(i,1,n) dist[i] = inf; 
    dist[S] = 0;pre[S]=0;
    Rep(i,1,n){
        int k = -1;
        Rep(j,1,n){
            if(vis[j]) continue;
            if(k == -1 || dist[k] > dist[j]) k = j;
        }
        vis[k] = true;
        Rep(j,1,n){
            if(vis[j]) continue;
            if(dist[j] > dist[k] + a[k][j]){
                dist[j] = dist[k] + a[k][j];
                pre[j] = k;
            }
        }
    }
}
vector<int> edge[maxn];
int fa[maxn];
int mx,pos[maxn];
inline int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
#define lson (o<<1)
#define rson ((o<<1|1))
int tag[maxn<<2];
void modify(int o,int l,int r,int x,int y,int v){
    if(l==x&&r==y){tag[o] = min(tag[o],v);return ;}
    int mid = (l + r) >> 1;
    if(y<=mid) modify(lson,l,mid,x,y,v); else
    if(mid+1<=x)modify(rson,mid+1,r,x,y,v); else{
        modify(lson,l,mid,x,mid,v);
        modify(rson,mid+1,r,mid+1,y,v);
    }
}
void build(int o,int l,int r){
    tag[o]=inf;
    if(l==r)return;
    int mid = (l+r)>>1;
    build(lson,l,mid);build(rson,mid+1,r);
}
int query(int o,int l,int r,int x){
    if(l==r) return tag[o];
    int mid = (l+r)>>1;
    if(x<=mid) return min(query(lson,l,mid,x),tag[o]); else
               return min(query(rson,mid+1,r,x),tag[o]);
}
int main(){
    n = read(),m = read();
    Rep(i,1,n)Rep(j,1,n) a[i][j] = inf;
    Rep(i,1,m){
        int x = read(),y = read(),v = read();
        a[x][y] = a[y][x] = v;
    }
    dijkstra(n,dn);
    dijkstra(1,d1);
    Rep(i,1,n) fa[i] = pre[i];
    mx = 0;
    for(int i=n;i;i=pre[i]){
        pos[i] = ++mx;
        fa[i] = i;
        if(pre[i])
            a[i][pre[i]] = a[pre[i]][i] = inf;
    }
    build(1,1,n);
    Rep(i,1,n){
        Rep(j,1,n){
            if(i==j) continue;
            if(a[i][j] != inf){
                int w = min(dn[i] + d1[j] + a[i][j],dn[j]+d1[i]+a[i][j]);
                int x = pos[find(i)],y = pos[find(j)];
                if(x>y)swap(x,y);
                if(x==y) continue;
                modify(1,1,mx,x+1,y,w);
            }
        }
    }
    int ans = d1[n];
    Rep(i,2,n) ans = max(ans,query(1,1,mx,i));
    writeln(ans);
}