刷题记录:牛客NC22600Rinne Loves Dynamic Graph

传送门:牛客

题目描述:

Rinne 学到了一个新的奇妙的东西叫做动态图，这里的动态图的定义是边权可以随着操作而变动的图。
当我们在这个图上经过一条边的时候，这个图上所有边的边权都会发生变动。
定义变动函数 f(x) = 1/(1-x)
 ，表示我们在图上走过一条边后，图的边权变动情况。
这里指的“图的变动”的意思是将每条边的边权代入上函数，得到的值即为该次变动后的边权。
现在 Rinne 想要知道，在这个变动的图上从 1 到 n 的最短路径。
因为 Rinne 不喜欢负数，所以她只需要你输出经过的边权权值绝对值之和最小的那个值就可以了。
输出答案保留三位小数。
输入:
3 3
1 2 2
2 3 2
3 1 3
输出:
3.000

这道题有两种解法,一种是最短路dp,另外一种是分层图最短路

首先无论是那种解法,我们都要先发现我们的$a_n=1/(1-a_{n-1})$数列是一个循环数列,并且循环节是3(由不动点法可知??)

解法一:最短路dp

我们可以将这种想法当做记录每一个点性质的最短路.主要思想就是记录这个点在我们的最短路中的情况.比如我们的这道题,我们发现每经过一个点,我们接下来的边权就会因此改变,所以我们需要每一个点目前的边数情况,这样才能得出下一个边的长度.所以在此题中,我们需要将我们原本的最短路中的$dis$数组改一下就行,不仅记录到每一个点的最短路,而是记录到每一个点每一种状态的最短路

可以证明我们目前的状态对于我们的$dijkstra$的贪心思想并没有影响,因为对于每一个点来说,既然我们当前点的某一状态是最优的,那么我们的下一个邻接点由该状态转移过去的状态肯定也是有该点该状态转移过去的最优解(因为我们的状态转移是单一的)

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Node{
	int v;double w;
};
vector<Node>edge[maxn];
int n,m;
struct heapnode{
	int u;double d;int state;
	bool operator <(const heapnode &rhs) const {
		return d>rhs.d;
	}
};
int vis[10][maxn];double dis[10][maxn];
double get_dist(double w,int state) {
	if(state==0) return w;
	if(state==1) return 1/(w-1);
	else return (w-1)/w;
}
void Dij(int S) {
	priority_queue<heapnode>q;
	for(int i=1;i<=n;i++) {
		dis[0][i]=dis[1][i]=dis[2][i]=int_INF;
	}
	dis[0][S]=0;
	q.push({S,0,0});
	while(!q.empty()) {
		heapnode f=q.top();q.pop();
		int u=f.u,state=f.state;
		if(vis[state][u]) continue;
		vis[state][u]=1;
		for(int i=0;i<edge[u].size();i++) {
			int v=edge[u][i].v;
			double w=get_dist(edge[u][i].w,f.state);
			if(dis[(f.state+1)%3][v]>dis[f.state][u]+w) {
				dis[(f.state+1)%3][v]=dis[f.state][u]+w;
				q.push({v,dis[(f.state+1)%3][v],(f.state+1)%3});
			}
		}
	}
}
int main() {
	n=read();m=read();
	for(int i=1;i<=m;i++) {
		int u=read(),v=read(),w=read();
		edge[u].push_back({v,(double)w});
		edge[v].push_back({u,(double)w});
	}
	Dij(1);
	double ans=int_INF;
	for(int i=0;i<=2;i++) ans=min(ans,dis[i][n]);
	if(ans==int_INF) printf("-1\n");
	else printf("%.3lf\n",ans);
	return 0;
}

解法二:分成图跑最短路

因为这道题的状态只有循环的3种,所以为我们的分层图提供了一条可行之路.

对于每一种状态我们都建一层图.对于每一条边来说,我们都需要链接第一层图u和第二层图v,第二层图u和第三层图v,第三层图u和第一层图v.分别代表当前的边处于第一种状态,第二种状态,第三种状态.并且边是单向的,并且一层中的所有点不添加边.因为对于每一条边的状态来说,都是线性单向变化的,恰好对应我们的层与层的单向变化.并且对于每一种状态来说我们都可以经过这条边转移到其他状态.然后最终只要在分层图中跑我们的最短路,求出跑到$n,2\ast n,3\ast n$的点即可.取一个min

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 300100
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Node{
	int v;double w;
};
vector<Node>edge[maxn];
int n,m;
double dis[maxn];int vis[maxn];
struct heapnode{
	int u;double d;
	bool operator<(const heapnode &rhs) const {
		return d>rhs.d;
	}
};
void Dij(int S) {
	priority_queue<heapnode>q;
	for(int i=1;i<=3*n;i++) dis[i]=int_INF;
	dis[S]=0;
	q.push({S,0});
	while(!q.empty()) {
		heapnode f=q.top();q.pop();
		int u=f.u;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0;i<edge[u].size();i++) {
			int v=edge[u][i].v;
			if(dis[v]>dis[u]+edge[u][i].w) {
				dis[v]=dis[u]+edge[u][i].w;
				q.push({v,dis[v]});
			}
		}
	}
}
int main() {
	n=read();m=read();
	for(int i=1;i<=m;i++) {
		int u=read(),v=read(),w=read();
		edge[u].push_back({v+n,(double)w});
		edge[v].push_back({u+n,(double)w});
		edge[u+n].push_back({v+2*n,1/((double)w-1)});
		edge[v+n].push_back({u+2*n,1/((double)w-1)});
		edge[u+2*n].push_back({v,((double)w-1)/(double)w});
		edge[v+2*n].push_back({u,((double)w-1)/(double)w});
	}
	Dij(1);
	double ans=int_INF;
	for(int i=0;i<=2;i++) ans=min(ans,dis[n+i*n]);
	if(ans==int_INF) printf("-1\n");
	else printf("%.3lf\n",ans);
	return 0;
}