「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$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#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\n",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();
}