题解：UVA567 Risk

Hhy140516 · 2025-08-08 22:00:19 · 题解

题目传送门

题意

有 20 个国家，给定第 i 个国家能到的国家情况，这样的情况边权是 1。

问点 u 到 v 的最短路径的长度。

分析

发现 n\le100，考虑 floyd。

floyd 是通过动态的思想来求解多源最短路的算法。首先选中一个点，把这个点看作中间需要经过的点，再枚举需要求的起点和终点，看是否进行松弛操作。

时间复杂度 O(n^3)，空间 O(n^2)。20 的数据量可以考虑此算法。

注意

由于样例输出错误，正确的输出方式详见我的代码。

代码

//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 100 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
    int u , w ;
};
struct Edgeve
{
    int v , w ;
};
struct node
{
  int x , y , id ;
}Node[kMaxN] ;
int n ;
int f[kMaxN][kMaxN] ;
inline ll ksm(ll a , ll b)
{
    ll mul = 1 ;
    while(b)
    {
        if(b & 1) mul *= a , mul %= MOD ;
        a *= a ;
        a %= MOD ;
        b >>= 1 ;
    }
    return mul ;
}
void work()
{
    int T = 0 ;
  while(cin >> n)
  {
    // 初始化
    memset(f , 0x3f , sizeof f) ;
        for( int i = 1 ; i <= 20 ; i++ ) f[i][i] = 0 ;
    for( int i = 1 ; i <= 19 ; i++ )
    {
        for( int j = 1 ; j <= n ; j++ )
        {
            int x ;
            cin >> x ;
            f[i][x] = f[x][i] = 1 ; // 记录答案
            }
            cin >> n ;
        }
        printf("Test Set #%d\n" , ++T) ;
        for( int k = 1 ; k <= 20 ; k++ ) for( int i = 1 ; i <= 20 ; i++ ) for( int j = 1 ; j <= 20 ; j++ ) f[i][j] = min(f[i][j] , f[i][k] + f[k][j]) ; // 松弛
        while(n--)
        {
            int u , v ;
            cin >> u >> v ;
            printf("%2d to %2d: %d\n" , u , v , f[u][v]) ; // 注意
        }
    putchar('\n') ; // 注意
    }
}
signed main()
{
//  freopen(".in" , "r" , stdin) ;
//  freopen(".out" , "w" , stdout) ;
//  ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}