题目

题目描述

Farmer John 的 N 头奶牛，编号为 (1…N)，站成一行（(1≤N≤5⋅10^4)）。第 (i) 头奶牛的品种编号为 (b_i)，范围为 (1…K)，其中 (1≤K≤50)。奶牛们需要你帮助求出如何最优地从奶牛 (1) 传输一条信息到奶牛 (N)。

从奶牛 (i) 传输信息到奶牛 (j) 花费时间 (|i−j|)。然而，不是所有品种的奶牛都愿意互相交谈，如一个 (K×K) 的方阵 (S) 所表示，其中如果一头品种 (i) 的奶牛愿意传输一条信息给一头品种 (j) 的奶牛，那么 (S_{ij}=1)，否则为 (0)。不保证 (S_{ij}=S_{ji})，并且如果品种 (i) 的奶牛之间不愿意互相交流时可以有 (S_{ii}=0)。

请求出传输信息所需的最小时间。

输入格式

输入的第一行包含 (N) 和 (K)。

下一行包含 (N) 个空格分隔的整数 (b_1,b_2,…,b_N)。

以下 (K) 行描述了方阵 (S)。每行包含一个由 (K) 个二进制位组成的字符串，从上往下第 (i) 个字符串的第 (j) 位为 (S_{ij})。

输出格式

输出一个整数，为需要的最小时间。如果不可能从奶牛 (1) 传输信息至奶牛 (N)，输出 (−1)。

输入输出样例

输入 #1
5 4
1 4 2 3 4
1010
0001
0110
0100
输出 #1
6
说明/提示

最优传输序列为 (1→4→3→5)。总时间为 (|1−4|+|4−3|+|3−5|=6)。

测试点性质：

测试点 1-5 满足 (N≤1000)。

测试点 6-13 没有额外限制。

供题：Dhruv Rohatgi

思路

建图(分层图),最短路.

对于(k)个颜色,开(k)层,每层有(n)个点.

对于每个颜色层,层内相邻点连一条权值为1的无向边.

对于每一只奶牛(i),设它的种类为(x),(y)是另一个种类.

连一条有向边: 奶牛$i o (第)x(层第)i$个点, 边权为0
若(s_{y,x}=1)连一条有向边: 第(y)层第(i)个点( o)奶牛(i), 边权为0

总点数(n+ncdot k),总边数(一条有向边按两条无向边算)不超过(ncdot k+2ncdot k).

求奶牛(1)到奶牛(n)的最短路即可.

最短路貌似可以双端队列实现(O(ncdot k)),但是本人又懒又菜就写了SPFA

代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	return negt ? -re : re;
}
const int N = 50010 , K = 100;

struct EDGE {
	int to , nxt , val;
}ed[(N * K + N) * 2];
int head[N + N * K];
void addedge(int u , int v , int val) {
	static int cnt = 0;
	++cnt;
	ed[cnt].to = v , ed[cnt].val = val , ed[cnt].nxt = head[u] , head[u] = cnt;
}

int n , k;
int col[N];
int s[K][K];

queue <int> q;
bool inq[N + N * K];

int cowid[N] , colid[K][N];//cow_id , color_id
int dist[N * K + N];
int newid() {
	static int cnt = 0;
	return ++cnt;
}
int main() {
	freopen("data//P7297_6.in" , "r" , stdin);
	n = read() , k = read();
	for(int i = 1 ; i <= n ; i++)
		col[i] = read();
	for(int i = 1 ; i <= k ; i++)
		for(int j = 1 ; j <= k ; j++) {
			char c = getchar();
			while(c != '0' && c != '1')	c = getchar();
			s[i][j] = c - '0';
		}
	
	//Get ID
	for(int i = 1 ; i <= n ; i++)
		cowid[i] = newid();
	for(int i = 1 ; i <= k ; i++)
		for(int j = 1 ; j <= n ; j++)
			colid[i][j] = newid();
	//build
	for(int i = 1 ; i <= k ; i++)
		for(int j = 1 ; j < n ; j++)
			addedge(colid[i][j] , colid[i][j + 1] , 1) , addedge(colid[i][j + 1] , colid[i][j] , 1);
	for(int i = 1 ; i <= n ; i++)
		addedge(cowid[i] , colid[col[i]][i] , 0);
	for(int i = 1 ; i <= n ; i++)
		for(int j = 1 ; j <= k ; j++)
			if(s[j][col[i]])
				addedge(colid[j][i] , cowid[i] , 0);
	
	//SPFA
	memset(dist , 0x3f , sizeof(dist));
	dist[cowid[1]] = 0;
	q.push(cowid[1]) , inq[cowid[1]] = true;
	while(!q.empty()) {
		int u = q.front();
		q.pop() , inq[u] = false;
		for(int i = head[u] ; i ; i = ed[i].nxt) {
			int v = ed[i].to;
			if(dist[v] > dist[u] + ed[i].val) {
				dist[v] = dist[u] + ed[i].val;
				if(!inq[v])
					q.push(v) , inq[v] = true;
			}
		}
	}
	printf("%d" , dist[cowid[n]] == 1061109567 ? -1 : dist[cowid[n]]);
	return 0;
}