Codeforces Gym Joyride（分层图，dijkstra）

题意：有一张图，每条边有一个边权t表示经过所花时间，每个点有两个权t、p，分别表示经过该点所花时间和所花费用，要求找一条路径，从点1出发再回到点1，所花时间恰好为x且费用最小，输出其费用，找不到则输出“It is a trap.”

思路：这题的解法和之前一场网络赛碰到的L题异曲同工，那题的题意是有k次机会把一条路的边权置为0，求最短路。我们可以把它抽象成分层图，即用二维的dis数组，dis[i][j]表示到点i且状态为j的最小花费。具体到题目来说，就是到点i且剩下j次机会的最小花费。也就是说，一个点，可以选择用或不用“边权置0”操作，转移到它连接的下一个点，相当于转移出两个状态。

而回到这一题，我们定义dis[i][j]表示到点i且还剩下j时间要走状态下的最小花费，由于这题可以在一个点一直停留，所以dis[u][x]可以转移到dis[u][x-u.t]和dis[v][x-w-v.t]。

这题加深了我对dijkstra最短路的理解。跑dij的过程其实可以看成DP的过程。和传统的最短路相比，可以理解为它一个点转移到其他点的状态变多了。思想大概如此，具体实现见代码

#include<iostream>

#include<cstdio>

#include<vector>

#include<queue>

#include<map>

#include<algorithm>

#include<cstring>

#include<string>

#include<cmath>

#include<set>

#include<functional>

#include<climits>

#include<cstdlib>

#include<climits>

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define de(x) cout<<#x<<" = "<<x<<endl

#define dd(x) cout<<#x<<" = "<<x<<" "

#define Clear(x,y) memset(x,y,sizeof(x))

using namespace std;

typedef long long ll;

typedef long double ld;

typedef pair<int,int> P;

typedef vector<int> V;

typedef map<int,int> M;

typedef set<int> S;

typedef queue<int> Q;

typedef priority_queue<int> BQ;

typedef set<int> S;

const double eps=1e-8,pi=acos(-1);

const int maxn=5e3+100,mod=1e9+7,INF=0x3f3f3f3f;

struct node

{

	int u,x,d;

	node(int a,int b,int c):u(a),x(b),d(c){}

	bool operator > (const node& no) const

	{

		return d>no.d;

	}

};

typedef priority_queue<node,vector<node>,greater<node> > SQ;

P edge[maxn],vec[maxn];

bool vis[maxn][maxn];

int dis[maxn][maxn],head[maxn],cnt;

void add(int u,int v)

{

	edge[++cnt].se=head[u];

	edge[cnt].fi=v;

	head[u]=cnt;

}

void dij(int s,int x,int w)

{

	Clear(dis,INF);

	SQ q;

	if (x-vec[s].fi<0)

		return;

	dis[s][x-vec[s].fi]=vec[s].se;

	q.push(node(s,x-vec[s].fi,vec[s].se));

	while (!q.empty())

	{

		node p=q.top();

		q.pop();

		int u=p.u,x=p.x,d=p.d;

		if (vis[u][x])

			continue;

		vis[u][x]=1;

		if (x-vec[u].fi>=0&&dis[u][x] + vec[u].se < dis[u][x-vec[u].fi])

		{

			dis[u][x-vec[u].fi] = dis[u][x] + vec[u].se;

			q.push(node(u, x-vec[u].fi, dis[u][x-vec[u].fi]));

		}

		for (int i=head[u];i;i=edge[i].se)

		{

			int v=edge[i].fi;

			if (x - vec[v].fi - w >= 0 && dis[u][x] + vec[v].se < dis[v][x-vec[v].fi-w])

			{

				dis[v][x-vec[v].fi-w] = dis[u][x] + vec[v].se;

				q.push(node(v, x-vec[v].fi-w, dis[v][x-vec[v].fi-w]));

			}

		}

	}

}

int main()

{

	int n,m,x,w;

	scanf("%d%d%d%d",&x,&n,&m,&w);

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

	{

		int u,v;

		scanf("%d%d",&u,&v);

		add(u,v);

		add(v,u);

	}

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

		scanf("%d%d",&vec[i].fi,&vec[i].se);

	dij(1,x,w);

	if (dis[1][0]==INF)

		printf("It is a trap.");

	else

		printf("%d",dis[1][0]);

	return 0;

}

巴特西

Codeforces Gym Joyride（分层图，dijkstra）

而回到这一题，我们定义dis[i][j]表示到点i且还剩下j时间要走状态下的最小花费，由于这题可以在一个点一直停留，所以dis[u][x]可以转移到dis[u][x-u.t]和dis[v][x-w-v.t]。

最新文章

热门文章