BEIJING EC2012 冻结

wjh15101051's space

卧薪尝胆，厚积薄发。

BEIJING EC2012 冻结

Date: Tue Jul 24 21:58:54 CST 2018

In Category: NoCategory

Description：

一共有 $ K $ 张可以减少某条道路一半通过时间的卡片，求出在可以使用这不超过 $ K $ 张时间卡片之情形下，从城市 $1 $ 到城市 $N$ 最少需要多长时间。

$1\le N,K \le 50$ $1\le M \le 1000$

Solution：

建出一张 $k+1$ 层的图，一层图中是原本的图，层之间是减少长度的边，求出从第 $0$ 层的 $1$ 号点到所有层的 $n$ 号点的最短路取 $min$ 。

这样可以保证使用不超过 $k$ 张卡片。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

int n,m,k;

#define MAXN 51

int d[MAXN * MAXN];

bool v[MAXN * MAXN];

priority_queue< pair<int,int> > q;

#define MAXM 1010

struct edge

{

	int to,nxt,v;

}e[MAXM * MAXN * 4];

int edgenum = 0;

int lin[MAXN * MAXN] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

void dijkstra()

{

	memset(d,0x3f,sizeof(d));

	d[1] = 0;

	q.push(make_pair(0,1));

	memset(v,false,sizeof(v));

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(v[k])continue;

		v[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				d[e[i].to] = d[k] + e[i].v;

				q.push(make_pair(-d[e[i].to],e[i].to));

			}

		}

	}

	return;

}

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	int a,b,c;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		for(int j = 0;j <= k;++j)

		{

			add(j * n + a,j * n + b,c);

			add(j * n + b,j * n + a,c);

			if(j < k)

			{

				add(j * n + a,(j + 1) * n + b,c / 2);

				add(j * n + b,(j + 1) * n + a,c / 2);

			}

		}

	}

	dijkstra();

	int res = 0x3f3f3f3f;

	for(int i = 0;i <= k;++i)

	{

		res = min(res,d[i * n + n]);

	}

	cout << res << endl;

	return 0;

}

In tag: 图论-分层图

wjh15101051