codevs P7117 高斯奥特曼的形态变化

背景:

有一天,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)) ;
			}
		}
	}
}

欢迎奥迷来看啊!!