UVA 10816 Travel in Desert ( 最小瓶頸生成樹 + 最短路徑 / 二分 + 最短路徑 )

UVa Online Judge
可以先依據邊的溫度求最小瓶頸生成樹，但這裡生成的條件是起點和終點為同一個連通分量即可。求出最小溫度後對這些邊求起點至終點的最短路徑就行了。無聊寫了SPFA跟Dijkstra，運行時間一模一樣。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 2;
const int MAXM = 1e4 + 4;
const double INF = 1e10;

struct UnionFind{
    int fa[MAXN];
    void init(int n){
        for(int i = 0; i <= n; ++i)
            fa[ i ] = i;
    }
    int find(int x){ return fa[x] == x ? x : fa[x] = find( fa[x] ); }
    bool same(int a, int b){
        int x = find( a ), y = find( b );
        return x == y;
    }
    bool unite(int a, int b){
        int x = find( a ), y = find( b );
        if( x == y ) return false;
        fa[ x ] = y; return true;
    }
} uf;

struct Edge{
    int u, v;
    double hot, dis;
    Edge(){}
    Edge(int _u, int _v, double _h, double _d): u(_u), v(_v), hot(_h), dis(_d){}
} es[MAXM];
bool cmpHot(const Edge &a, const Edge &b){
    return a.hot < b.hot;
}

int n, m;
int src, gol;
vector<Edge> G[MAXN];

struct Kruskal{
    void init(){
        uf.init( n );
        sort( es, es + m, cmpHot );
    }
    double solve(){
        double res;
        for(int i = 0; i < m; ++i)
            if( uf.unite( es[i].u, es[i].v ) ){
                res = es[i].hot;
                if( uf.same( src, gol ) ) break;
            }
        assert( uf.same( src, gol ) );
        return res;
    }
} mst;

/*
struct Dijkstra{
    double dis[MAXN];
    int vis[MAXN], pre[MAXN];
    void init(){
        fill( dis, dis + MAXN, INF );
        memset( vis, 0, sizeof(vis) );
        memset( pre, -1, sizeof(pre) );
    }
    void printPath(){
        stack<int> route;
        int u = gol; while( u != -1 ) route.push( u ), u = pre[ u ];
        for( ; !route.empty(); route.pop())
            printf("%d%c", route.top(), route.size() == 1 ? '\n' : ' ');
    }
    typedef pair<double, int> pdi;
    void solve(double mh){ // can only pass edges that are not hotter than mh
        priority_queue<pdi, vector<pdi>, greater<pdi> > pq;
        pq.push( pdi( dis[ src ] = 0.0, src ) );
        while( !pq.empty() ){
            int u = pq.top().second; pq.pop();
            if( vis[ u ] ) continue;
            vis[ u ] = 1;
            if( u == gol ) return;
            for(int i = 0; i < G[u].size(); ++i){
                int v = G[u][i].v;
                if( G[u][i].hot > mh ) continue;
                if( dis[ v ] > dis[ u ] + G[u][i].dis ){
                    dis[ v ] = dis[ u ] + G[u][i].dis;
                    pre[ v ] = u;
                    pq.push( pdi( dis[ v ], v ) );
                }
            }
        }
    }
} sp;
*/
struct SPFA{
    double dis[MAXN];
    int pre[MAXN], inq[MAXN];
    void init(){
        fill( dis, dis + MAXN, INF );
        memset( pre, -1, sizeof(pre) );
        memset( inq, 0, sizeof(inq) );
    }
    void printPath(){
        stack<int> route;
        int u = gol; while( u != -1 ) route.push( u ), u = pre[ u ];
        for( ; !route.empty(); route.pop())
            printf("%d%c", route.top(), route.size() == 1 ? '\n' : ' ');
    }
    void solve(double mh){
        queue<int> que;
        que.push( src );
        dis[ src ] = 0;
        while( !que.empty() ){
            int u = que.front(); que.pop();
            inq[ u ] = 0;
            for(int i = 0; i < G[u].size(); ++i){
                int v = G[u][i].v;
                if( G[u][i].hot > mh ) continue;
                if( dis[ v ] > dis[ u ] + G[u][i].dis ){
                    dis[ v ] = dis[ u ] + G[u][i].dis;
                    pre[ v ] = u;
                    if( !inq[ v ] ) que.push( v );
                }
            }
        }
    }
} spfa;

void solve(){
    mst.init();
    double max_hot = mst.solve(); // max hot of min - hot - spanning tree
    spfa.init();
    spfa.solve( max_hot );
    spfa.printPath();
    printf("%.1lf %.1lf\n", spfa.dis[ gol ], max_hot);
}

void init(){
    for(int i = 0; i <= n; ++i)
        G[i].clear();
}

int main(){
    while( scanf("%d%d", &n, &m) == 2 ){
        init();
        scanf("%d%d", &src, &gol);
        for(int i = 0; i < m; ++i){
            int u, v; double h, d; scanf("%d%d%lf%lf", &u, &v, &h, &d);
            es[ i ] = Edge( u, v, h, d );
            G[ u ].push_back( Edge( u, v, h, d ) );
            G[ v ].push_back( Edge( v, u, h, d ) );
        }
        solve();
    }
    return 0;
}

另外還可以二分枚舉一個熱度值，求兩端點距離，檢查是否可以達到。或許有輕鬆一點點。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 2;
const int MAXM = 1e4 + 4;
const double INF = 1e10;

struct Edge{
    int u, v; double hot, dis;
    Edge(){}
    Edge(int _u, int _v, double _h, double _d): u(_u), v(_v), hot(_h), dis(_d){}
} es[MAXM];
bool cmpHot(const Edge &a, const Edge &b){
    return a.hot < b.hot;
}

int n, m;
int src, gol;
vector<Edge> G[MAXN];

struct SPFA{
    double dis[MAXN];
    int pre[MAXN], inq[MAXN];
    void init(){
        fill( dis, dis + MAXN, INF );
        memset( pre, -1, sizeof(pre) );
        memset( inq, 0, sizeof(inq) );
    }
    void printPath(){
        stack<int> route;
        int u = gol; while( u != -1 ) route.push( u ), u = pre[ u ];
        for( ; !route.empty(); route.pop())
            printf("%d%c", route.top(), route.size() == 1 ? '\n' : ' ');
    }
    bool ok(double mh){ // cannot pass edge hot > mh
        queue<int> que;
        que.push( src );
        dis[ src ] = 0.0;
        while( !que.empty() ){
            int u = que.front(); que.pop();
            inq[ u ] = 0;
            if( u == gol ) return true;
            for(int i = 0; i < G[u].size(); ++i){
                int v = G[u][i].v;
                if( G[u][i].hot > mh ) continue;
                if( dis[ v ] > dis[ u ] + G[u][i].dis ){
                    dis[ v ] = dis[ u ] + G[u][i].dis;
                    pre[ v ] = u;
                    if( !inq[ v ] ) que.push( v ), inq[ v ] = 1;
                }
            }
        }
        return false;
    }
} sp;

void solve(){
    double lb = 0.0, rb = 50.0;
    while( rb - lb > 1e-3 ){
        double mid = ( lb + rb ) / 2.0;
        sp.init();
        if( sp.ok( mid ) ) rb = mid;
        else lb = mid;
    }
    sp.init();
    assert( sp.ok( rb ) ); // make sure the path is ok
    sp.printPath();
    printf("%.1lf %.1lf\n", sp.dis[ gol ], rb);
}

void init(){
    for(int i = 0; i <= n; ++i)
        G[i].clear();
}

int main(){
    while( scanf("%d%d%d%d", &n, &m, &src, &gol) == 4 ){
        init();
        for(int i = 0; i < m; ++i){
            int u, v; double h, d;
            scanf("%d%d%lf%lf", &u, &v, &h, &d);
            es[i] = Edge( u, v, h, d );
            G[ u ].push_back( es[i] );
            G[ v ].push_back( Edge( v, u, h, d ) );
        }
        solve();
    }
    return 0;
}