题解 P1186 【玛丽卡】

见大佬们都是用的SPFA

为了关心Dijkstra党，所以这里写一篇关于Dijkstra的题解

主要思路：

这个题意实在是太模糊了，我也是听了大佬的解释才明白的。

我可以再次翻译一遍题意QAQ：

找出在一条边断掉的情况下的单源最短路径，并输出最坏的情况（去边不同会影响最短路）。

完了？？？

完了。。。

所以思路就出来了：一一去掉所有边，分别去求最短路。

仔细想想：时间复杂度（Dijkstra）O(n^2*m)

如果是dalao写带堆优化的也会到 O(nlogn*m)

代码如下（提示：这个只有80分哦，至于为什么，看复杂度啊）

代码1:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define rep(i, x) for (int i = h[x]; i; i = e[i].nxt)
#define mn 1010
#define inf 1 << 30
#define ll long long
#define ld long double
#define fi first
#define se second
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
inline int read(){
    int f = 1, x = 0;char ch = getchar();
    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}
inline void write(int x){
    if (x < 0)putchar('-'),x = -x;
    if (x > 9)write(x / 10);
    putchar(x % 10 + '0');
}
//This is AC head above...
struct edge{
    int v,nxt,w;
} e[(mn * (mn-1)) >>1];
int h[mn],p;
inline void add(int a,int b,int c){
    p++;
    e[p].nxt=h[a];
    h[a]=p;
    e[p].v = b;
    e[p].w = c;
}
//Dij + 堆优化
struct node{
    int u,v;
    bool operator <(const node &b) const{
        return u > b.u;
    }
};//重载运算符
int n,m,s,pp;
int dis[mn];//起点到每个点的距离
int pre[mn], per[mn];
inline void Dij(){//s为起点
    int s = 1;
    priority_queue<node> q;//优先队列
    go(i, 0, n, 1)
        dis[i] = inf;
    dis[s] = 0;
    node o;
    o.u = 0;
    o.v = s;
    q.push(o);
    while (q.size()){
        int u = q.top().v;
        int d = q.top().u;
        q.pop();
        if(d!=dis[u])//玄学的优化不解释
            continue;//据说有这个优化可以用Dijkstra+堆优化过P4779
        rep(i,u){
            int v = e[i].v;
            int w = e[i].w;
            if (dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                node ppp;
                ppp.u = dis[v], ppp.v = v;
                q.push(ppp);
            }
        }
    }
}
int maxx=-1;
int main(){
    n = read(), m = read();
    go(i,1,m,1){
        int x = read(), y = read(), z = read();
        add(x, y, z);
        add(y, x, z);
    }
    go(i,1,m*2,1){//每一条边（注意是2*m）删掉，跑一边最短路，求之中最大值
        int r = e[i].w;
        e[i].w = inf;
        Dij();
        //cout << dis[n] << " ";
        maxx = max(maxx, dis[n]);
        e[i].w = r;//类似回溯的东东
    }
    //cout << "\n";
    cout << maxx;
    return 0;
}

不过时间复杂度太高了！！！怎么办？？？

不慌，~~慌也没用~~。

我们不是分析过题吗？去掉一条边的单源最短路。如果去的边不是不删边情况下的单源最短路径上的边，那么会对最终答案有影响吗？

没有！

所以，我们只需要看一看单源最短路上的边分别去掉会是什么情况就可以了。正常操作是先跑一遍Dijkstra（最短路），然后再去记录单源最短路上经过的边，把路过的边分别去掉，分别跑一边单源最短路取最大值就好啦！

所以，代码如下：（在记录路过的边和删边上我会在注释里解释的QwQ）

代码2：