题解 P2176 【[USACO14FEB]路障Roadblock】

xsap · 2020-01-07 18:57:00 · 题解

• 这题SPFA会被卡吗?(实测好像并不会，也没有比Dijkstra慢很多)

• 纯暴力思路就是枚举每一条边，之后将这条边边权翻倍。时间复杂度O(E × 最短路复杂度 )，用SPFA可能会被卡，dijkstra直接爆炸
• 优化的思路是显然，草堆只可能放在最短路上，所以每次判断一条边是否在最短路上，如果是，才跑最短路，这样程序效率会快很多，SPFA也不会被卡，当然，因为是全正边，所以肯定跑Dijkstra
• 至于如何判断是否在1-n的最短路上。方法是：先跑一次以1为源点的最短路，记到数组dis[1][i]中；再跑一次以 n为源点的最短路，记到 dis[2][i] 中；每次检查一条i -> j的边，就看dis[1][i] + g[i][j] + dis[2][j] = dis[1][n] 吗。
• 最好用邻接矩阵存，这样更易于翻倍边权。
• 代码：（Dijkstra）

# include <iostream>
# include <cstdio>
# include <set>

using namespace std ;

int n , m ;
int g[105][105] ;
set < pair< int , int > > heap ;
int dis[4][40005] ;

void dij( int s , int tmp )
{
    while ( heap.size() )
    {
        heap.erase( heap.begin() ) ;
    }
    for ( int i = 1 ; i <= n ; i++ )
        dis[tmp][i] = 1e9 + 5 ;
    dis[tmp][s] = 0 ;
    heap.insert( make_pair( dis[tmp][s] , s ) ) ;
    for ( int i = 1; i <= n ; i++ )
    {
        int x = heap.begin() -> second ;
        int d = heap.begin() -> first ;
        heap.erase( make_pair( d , x ) ) ;
        for ( int j = 1 ; j <= n ; j++ )
        {
            if ( dis[tmp][x] + g[x][j] >= dis[tmp][j] )
                continue ;
            heap.erase( make_pair( dis[tmp][j] , j ) ) ;
            dis[tmp][j] = dis[tmp][x] + g[x][j] ;
            heap.insert( make_pair( dis[tmp][j] , j ) ) ;
        }
    }
    return ;
}

int main()
{
    for ( int i = 1 ; i <= 100 ; i++ )
        for ( int j = 1 ; j <= 100 ; j++ )
            g[i][j] = 1000000000 ;
    scanf("%d%d" , &n , &m) ;
    for ( int i = 1 ; i <= m ; i++ )
    {
        int x , y , z ;
        scanf("%d%d%d" , &x , &y , &z) ;
        g[x][y] = z ;
        g[y][x] = z ;
    }
    dij( 1 , 1 ) ;
    dij( n , 2 ) ;
    int ans = 0 ;
    for ( int i = 1 ; i <= n ; i++ )
    {
        for ( int j = 1; j <= n ; j++ )
        {
            if ( dis[1][i] + g[i][j] + dis[2][j] == dis[1][n] )
            {
                g[i][j] *= 2 ;
                g[j][i] *= 2 ;
                dij( 1 , 3 ) ;
                g[i][j] /= 2 ;
                g[j][i] /= 2 ;
                ans = max( ans , dis[3][n] - dis[1][n] ) ;
            }
        }
    }
    printf("%d\n" , ans) ;
    return 0 ;
}

• SPFA版

# include <iostream>
# include <cstdio>
# include <set>
# include <queue>

using namespace std;

int n , m ;
int g[105][105] ;
int dis[4][40005] ;
bool already[105] ;
queue < int > q ;

void spfa( int s , int tmp )
{
    for ( int i = 1 ; i <= n ; i++ )
    {
        dis[tmp][i] = 1e9 + 5 ;
        already[i] = false ;
    }
    already[s] = 1 ;
    dis[tmp][s] = 0 ;
    q.push( s ) ;
    while ( ! q.empty() )
    {
        int x = q.front() ;
        already[x] = 0 ;
        q.pop() ;
        for ( int y = 1 ; y <= n ; y++ )
        {
            if ( dis[tmp][x] + g[x][y] >= dis[tmp][y] )
                continue ;
            dis[tmp][y] = dis[tmp][x] + g[x][y] ;
            if ( already[y] )
                continue ;
            already[y] = 1 ;
            q.push( y ) ;
        }
    }
}

int main()
{
    for ( int i = 1 ; i <= 100 ; i++ )
        for ( int j = 1 ; j <= 100 ; j++ )
            g[i][j] = 1000000000 ;
    scanf("%d%d" , &n , &m) ;
    for ( int i = 1 ; i <= m ; i++ )
    {
        int x , y , z ;
        scanf("%d%d%d" , &x , &y , &z) ;
        g[x][y] = z ;
        g[y][x] = z ;
    }
    spfa( 1 , 1 ) ;
    spfa( n , 2 ) ;
    int ans = 0 ;
    for ( int i = 1 ; i <= n ; i++ )
    {
        for ( int j = 1; j <= n ; j++ )
        {
            if ( dis[1][i] + g[i][j] + dis[2][j] == dis[1][n] )
            {
                g[i][j] *= 2 ;
                g[j][i] *= 2 ;
                spfa( 1 , 3 ) ;
                g[i][j] /= 2 ;
                g[j][i] /= 2 ;
                ans = max( ans , dis[3][n] - dis[1][n] ) ;
            }
        }
    }
    printf("%d\n" , ans) ;
    return 0 ;
}