专栏文章

题解:UVA567 Risk

UVA567题解参与者 1已保存评论 1

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miog00zn
此快照首次捕获于
2025/12/02 18:35
3 个月前
此快照最后确认于
2025/12/02 18:35
3 个月前
查看原文

题意

2020 个国家,给定第 ii 个国家能到的国家情况,这样的情况边权是 11
问点 uuvv 的最短路径的长度。

分析

发现 n100n\le100,考虑 floyd
floyd 是通过动态的思想来求解多源最短路的算法。首先选中一个点,把这个点看作中间需要经过的点,再枚举需要求的起点和终点,看是否进行松弛操作。
时间复杂度 O(n3)O(n^3),空间 O(n2)O(n^2)2020 的数据量可以考虑此算法。

注意

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

代码

CPP
//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 ;
}



评论

1 条评论,欢迎与作者交流。

正在加载评论...