求助dp+hash

// Problem: P3686 [CERC2016]鐖靛＋涔嬫梾 Jazz Journey
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3686
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=300005;
ll n,d,a[N],f[N],m;
ull get_hash(ull u,ull v,char t){
	ull ans=0;
	ans=u+v*n+t*n*n;
	return ans;
}
map<ull,int>ticket;
int main(){
	cin>>n>>d;
	for (int i=1;i<=d;i++)
		cin>>a[i];
	cin>>m;
	for (int i=1;i<=m;i++){
		int u,v,p;
		char t;
		cin>>u>>v>>t>>p;
		ull temp1=get_hash(u,v,t);
		ull temp2=get_hash(u,v,'O');
		if (ticket.find(temp1)!=ticket.end()){
			if (ticket[temp1]>p)
				ticket[temp1]=p;
		}
		else{
			ticket[temp1]=p;
		}
		if (ticket.find(temp2)!=ticket.end()){
			if (ticket[temp2]>p)
				ticket[temp2]=p;
		}
		else{
			ticket[temp2]=p;
		}
	}
	for (int i=2;i<=d;i++){
		ull temp1=get_hash(a[i-1],a[i],'O');
		ull temp2=get_hash(a[i-2],a[i-1],'R');
		ll t1=ticket[temp1],t2=ticket[temp2];
		if (t1<=0) t1=999999;
		if (t2<=0) t2=999999;
		f[i]=f[i-1]+t1;
		if (a[i-2]==a[i]) 
			f[i]=min(f[i],f[i-2]+t2);
	}
	cout<<f[d];
	return 0;
}