2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training5

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training5 [2021/05/19 20:08]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training5 [2021/05/19 22:47] (当前版本)
jxm2001
@@ 行 86: / 行 86: @@
 </code>
 </hidden>
+=====  J. Journey from Petersburg to Moscow =====
+==== 题意 ====
+给定边权图，求从点 $1$ 到点 $n$ 的最短路。其中如果路径边数超过 $k$ 则仅最大的 $k$ 条边对路径长度产生贡献。
+==== 题解 ====
+设路径边权从大到小依次为 $c_1,c_2\cdots c_k,c_{k+1}\cdots c_t$，设新路径长度函数为 $f(x)=kx+\sum_{i=1}^t \max(c_i-x,0)$。
+不难发现该函数在 $x\in [c_{k+1},c_k]$ 时取到最小值，且此时函数值恰好等于最大的 $k$ 条边对路径长度产生贡献。
+于是不妨枚举所有 $c_k$，对边权做变换 $w\to w-c_k$，然后跑最短路，求所有结果的最小值。
+另外需要考虑路径长度小于 $k$ 的情况，直接最短路算法即可，为了减少分类讨论也可以令此时 $c_k=0$。总时间复杂度 $O(m^2\log m)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=3005,MAXM=3005;
+const LL inf=1e15;
+struct Edge{
+	int to,w,next;
+}edge[MAXM<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v,int w){
+	edge[++edge_cnt]=Edge{v,w,head[u]};
+	head[u]=edge_cnt;
+}
+struct{
+	int u,v,w;
+}edge2[MAXM];
+int ww[MAXM];
+struct Node{
+	LL dis;
+	int u;
+	bool operator < (const Node &b)const{
+		return dis > b.dis;
+	}
+};
+LL dis[MAXN];
+bool vis[MAXN];
+LL solve(int n,int m,int k,int minw){
+	_rep(i,1,n)head[i]=0,dis[i]=inf,vis[i]=false;
+	edge_cnt=0;
+	_for(i,0,m){
+		Insert(edge2[i].u,edge2[i].v,max(edge2[i].w-minw,0));
+		Insert(edge2[i].v,edge2[i].u,max(edge2[i].w-minw,0));
+	}
+	priority_queue<Node> q;
+	dis[1]=0;
+	q.push(Node{dis[1],1});
+	while(!q.empty()){
+		int u=q.top().u;q.pop();
+		if(vis[u])continue;
+		vis[u]=true;
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(dis[u]+edge[i].w<dis[v]){
+				dis[v]=dis[u]+edge[i].w;
+				q.push(Node{dis[v],v});
+			}
+		}
+	}
+	return dis[n]+1LL*k*minw;
+}
+int main()
+{
+	int n=read_int(),m=read_int(),k=read_int();
+	_for(i,0,m){
+		edge2[i].u=read_int();
+		edge2[i].v=read_int();
+		ww[i]=edge2[i].w=read_int();
+	}
+	sort(ww,ww+m);
+	int m2=unique(ww,ww+m)-ww;
+	LL ans=inf;
+	_for(i,0,m2)
+	ans=min(ans,solve(n,m,k,ww[i]));
+	enter(min(ans,solve(n,m,k,0)));
+	return 0;
+}
+</code>
+</hidden>

2020-2021/teams/legal_string/jxm2001/contest/2021_buaa_spring_training5.1621426089.txt.gz · 最后更改: 2021/05/19 20:08 由 jxm2001