专栏文章
题解:UVA567 Risk
UVA567题解参与者 1已保存评论 1
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @miog00zn
- 此快照首次捕获于
- 2025/12/02 18:35 3 个月前
- 此快照最后确认于
- 2025/12/02 18:35 3 个月前
题意
有 个国家,给定第 个国家能到的国家情况,这样的情况边权是 。
问点 到 的最短路径的长度。
分析
发现 ,考虑
floyd。floyd 是通过动态的思想来求解多源最短路的算法。首先选中一个点,把这个点看作中间需要经过的点,再枚举需要求的起点和终点,看是否进行松弛操作。时间复杂度 ,空间 。 的数据量可以考虑此算法。
注意
由于样例输出错误,正确的输出方式详见我的代码。
代码
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 条评论,欢迎与作者交流。
正在加载评论...