游客 注册 | 登录
中文 | En

3225 - 传送门

通过次数

0

提交次数

0

时间限制 : 10 秒 内存限制 : 128 MB

FJ 每天都要从家里去牧场，再从牧场回家……

FJ从家到牧场的地区可以看作一个N个点和M条双向边的图，家在1号点，牧场在N号点。现在FJ掌握了现代科技，他现在要将一些道路的两端修建双向传送的传送门，这样可以把通过的时间变为0。现在FJ最多可以建K个传送门，FJ想知道他从家到牧场最少需要多少时间？

题目输入

第一行，三个数N，M，K

接下来M 行，每行三个数，表示一条边的两端和长度

题目输出

一个数，表示最少要用多长时间

输入/输出样例

输入格式

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

输出格式

1

C++解答

/*
	author :hzoi_ztx
	title  :传送门 
	ALG    :双向spfa 
	comment:

	[2014 10 14 test]
*/

#include <cstdio>
#include <cstring>
#include <cctype>

#define  maxn  10005
#define  maxm  50005
#define  maxk  21
#define  info  0x7f7f7f7f
//#define  size  16419000
#define  size  1000000
int ret , ch ;

/*inline int qread() {
	ret = 0 ; while (!isdigit(ch = getchar())) ;
	while (ret = ret*10+ch-'0' , isdigit(ch = getchar())) ;
	return ret ;
}*/

struct FST{
	int to , next , len ;
} e[maxm*2] ; int star[maxn] = {0} , tot_e ;

void addEdge(int u , int v , int w) {
	tot_e ++ ; e[tot_e].to = v ; e[tot_e].len = w ;
	e[tot_e].next = star[u] ; star[u] = tot_e ;
}

int n , m , K ;
int u , v , w , k , p ;
int d[maxn][maxk] ;
bool b[maxn][maxk] = {0} ;

int q1[size] , q2[size] ;
int head = 0 , rear = -1 ;
int F(int x) { return ((x%size)+size)%size ; }
 bool empty() { return head == rear+1 ; }
 int front1() { return q1[F(head)] ; }
 int front2() { return q2[F(head)] ; }
 void push_front(int x , int y ) { head -- ; q1[F(head)] = x ; q2[F(head)] = y ; }
 void push_back(int x , int y ) { rear ++ ; q1[F(rear)] = x ; q2[F(rear)] = y ; }
 void pop_front() { head ++ ; }
 void pop_back() { rear -- ; }
 int qsize() { return rear-head+1 ; }
 int front11() { return q1[F(head+1)] ; }
 int front22() { return q2[F(head+1)] ; }

void spfa() {
	d[1][0] = 0 ;
	push_back(1 , 0) ;
	while (!empty()) {
		u = front1() ; k = front2() ; pop_front() ; b[u][k] = false ;
		p = star[u] ;
		while (p) {
			v = e[p].to ; w = e[p].len ;
			if (d[u][k]+w < d[v][k]) {
				d[v][k] = d[u][k]+w ;
				if (!b[v][k]) {
					b[v][k] = true ;
					if (d[v][k] < d[front1()][front2()]
						|| (qsize()>1 && d[v][k] < d[front11()][front22()])
					) push_front(v , k) ;
					else push_back(v , k) ;
				}
			}
			if (k<K &&d[u][k]<d[v][k+1]) {
				d[v][k+1] = d[u][k] ;
				if (!b[v][k+1]) {
					b[v][k+1] = true ;
					if (d[v][k+1] < d[front1()][front2()]
						|| (qsize()>1 && d[v][k+1] < d[front11()][front22()])
					) push_front(v , k+1) ;
					else push_back(v , k+1) ;
					
				}
			}
			p = e[p].next ;
		}
	}
}

int main() {
//	#define READ
	#ifdef  READ
		freopen("door.in" ,"r",stdin ) ;
		freopen("door.out","w",stdout) ;
	#endif
	memset(d , 0x7f , sizeof (d)) ;
//	n = qread() ;
//	m = qread() ;
//	K = qread() ;
scanf("%d%d%d", &n , &m , &K ) ;
	for (int i = m ; i > 0 ; i -- ) {
//		u = qread() ;
//		v = qread() ;
//		w = qread() ;
scanf("%d%d%d", &u , &v , &w ) ;
		addEdge(u , v , w) ;
		addEdge(v , u , w) ;
	}
	
	spfa() ;
	w = 0x7f7f7f7f ;
	for (int i = 0 ; i <= K ; i ++ ) {
		if (d[n][i] < w) w = d[n][i] ;
	}
	printf("%d\n", w ) ;
	return 0 ;
}
请先登陆