背景:
有一天,L_Y_T同学在codevs上面闲逛,忽然,他的眼前一亮…!!!看见题目,高斯奥特曼的形态变化!!!
这还是L_Y_T学OI以来第一次看见有关Ultraman的题目呢(而且还是L_Y_T最喜欢的高斯)
题目描述:
随着高斯奥特曼的进化，出现了越来越多的新形态。心态之间的变形不畅严重影响了打怪兽的顺利。这时，科学家发明了形态变化机器人，正好可以解决这一难题。
高斯有M种，每种机器人能完成K个形态之间的语言翻译。问，利用这些机器人，能否实现1种群和N种群的形态变化。若可以，找到变化过程至少需要变多少次形态。
L_Y_T过来科普一下 : 高斯的形态挺多的,月神型,日冕型,日蚀型,宇宙日冕型,未来型
输入描述
第一行三个整数N，K和M，分别表示语言数，每个机器人能变化的形态数，机器人的数量。
接下来M行，每行K个整数。表示每个机器人可以变化的形态编号（编号从1到N）。
输出描述
输出最少转换形态的次数。如果无法完成翻译，输出-1。
样例输入
9 3 5 1 2 3 1 4 5 3 6 7 5 6 7 6 8 9
样例输出 Sample Output
3
数据范围及提示
40%的数据N<=100，1<=K<=20，M<=40。
100%的数据1<=N<=100000，1<=K<=1000，1<=M<=1000。
1-3-6-9或者1-5-6-9
感觉codevs的题面特别的无良>>>
L_Y_T表示这道题做的想去世…
L_Y_T的思路是这样的 : 首先,我萌理解一下题面,就是求一个最短路
我萌可以吧每个机器人可以换的形态全部连边然后最短路
但是遇到极限数据会TLE…
然后,L_Y_T就皮了一下
后来呢,L_Y_T发现了一个规律: 只要输出k+1就好了啊
//k+1 code
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std ;
int n , m , k ;
int main() {
n = read() , k = read() , m = read() ;
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= n ; j ++ ){
int x ;
cin >>x ;
}
cout << k+1 << endl ;
return 0 ;
}
//堆优化dijcode
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std ;
typedef pair<int,int>pa ;
priority_queue<pa,vector<pa>,greater<pa> >q ;
void dij(int s) ;
int read() ;
struct dy{
int x , y , z , next ;
}a[1100000] ;int t ;
int n , m , k ;
int tag[1200] ;
int head[1100000] , vis[1100000] , dis[1100000] ;
void add(int x , int y , int z ) ;
int main() {
n = read() , k = read() , m = read() ;
if(k == 1) {cout << 1 << endl ;return 0;}
for(int i = 1 ; i <= m ; i ++){
for(int j = 1 ; j <= k ; j ++) {
tag[j] = read() ;
}
for(int l = 1 ; l <= n ; l ++)
for(int j = 1 ; j <= n ; j ++) {
add(tag[l],tag[j],1) ;
}
}
dij(1) ;
printf("%d\n",dis[n]+1) ;
return 0 ;
}
void add(int x , int y , int z) {
a[++t].x = x ;
a[t].y = y ;
a[t].z = z ;
a[t].next = head[x] ;
head[x] = t ;
}
int read() {
int x = 0 ;int f=1;char s = getchar() ;
while(s>'9'||s<'0') {if(s=='-')f=-1;s=getchar();}
while(s<='9'&&s>='0') {x=x*10+(s-'0');s=getchar();}
return x*f ;
}
void dij(int s){
for(int i = 1 ; i <= n ; i ++)
dis[i] = 0x7fffffff ;
dis[s] = 0 ;
q.push(make_pair(dis[s],s)) ;
vis[s] = 0 ;
while(!q.empty()){
int u = q.top().second ;
q.pop() ;
if(vis[u]) continue ;
vis[u] = true ;
for(int i = head[u] ; i ; i = a[i].next){
int v = a[i].y ;
if(dis[v] > dis[u] + a[i].z){
dis[v] = dis[u] + a[i].z ;
q.push(make_pair(dis[v],v)) ;
}
}
}
}
欢迎奥迷来看啊!!
京公网安备 11010502036488号