「JOI 2021 Final」机器人

「JOI 2021 Final」机器人

原问题中颜色什么时候改没有影响

显然不能记录每条边的颜色，显然在行走过程中不会回到原先的点

因此考虑简化状态

从一个点出去时，走了一条边((u,v,c,w))，从(u)出发颜色为(c)的边(w)之和为(S_{u,c})，则有两种转移：

1.走过来时的边被改变了，权值(w)

2.改变了其他同种颜色的边，权值(S_{u,c}-w)

对于2情况在前面修改的边，在后面不会产生贡献（否则可以直接通过这条边过去，而不需要绕路）

可以直接转移到对应节点

1类转移的贡献相当于下次走这种颜色时，可以少改变一条边的颜色

即下一次转移2时，权值变为(S_{v,c}-w-w')

可以增加一个额外权值(-w)，然后对于下一个点(v)所有颜色为(c)的出边转移，这可以通过构建虚点解决

实际上总权值就是(0)

考虑到一种不合法的情况，即走回(u)，但是这样的转移权值就是(S_{v,c}-w'ge 0)

非法情况无影响

最终得到的转移就是一个非负边权的最短路图，可以跑(Dijkstra)解决

总点数(leq n+2m)，总边数(leq 6m)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)

char IO;
int rd(){
	int s=0;
	while(!isdigit(IO=getchar()));
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return s;
}

const int N=5e5+10,INF=1e9+10;

int n,m,k;
struct Edge{
	int v,c,w;
};
vector <Edge> G[N];
int U[N],V[N],C[N],W[N];

struct Node{
	int u; ll d;
	bool operator < (const Node __) const {
		return d>__.d;
	}
};
priority_queue <Node> que;
ll dis[N],S[N];
void Upd(int u,ll d){
	if(dis[u]<=d) return;
	dis[u]=d,que.push((Node){u,d});
}
map <int,int> st[N];
void AddEdge(int u,int v,int c,int w){
	if(!st[u].count(c)) {
		st[u][c]=++k;
		G[u].pb((Edge){k,0,0});
	}
	int t=st[u][c];
	G[t].pb((Edge){v,c,w}),S[t]+=w;
}

void Dijkstra(){
	memset(dis,63,sizeof dis);
	dis[1]=0,que.push((Node){1,0});
	while(!que.empty()) {
		int u=que.top().u; ll d=que.top().d; que.pop();
		if(dis[u]<d) continue;
		if(u<=n) {
			for(Edge dd:G[u]) {
				int t=dd.v;
				for(Edge i:G[t]) {
					Upd(i.v,d+min((ll)i.w,S[t]-i.w));
					Upd(st[i.v][i.c],d);
				}
			}
		} else for(Edge i:G[u]) Upd(i.v,d+S[u]-i.w);
	}
	printf("%lld
",dis[n]<1e17?dis[n]:-1);
}

int main(){
	freopen("robot.in","r",stdin),freopen("robot.out","w",stdout);
	n=rd(),m=rd(),k=n;
	rep(i,1,m) {
		int u=rd(),v=rd(),c=rd(),w=rd();
		AddEdge(u,v,c,w),AddEdge(v,u,c,w);
	}
	Dijkstra();
}