tesourodeturtur.cpp

#include <bits/stdc++.h>
#define MAX 205000
using ll = long long;
typedef std::pair<int,int> pii;
std::map<pii,std::vector<pii>> conexoes;
typedef std::pair<ll,pii> pli;
bool passa[MAX];
int chaves[MAX];
std::map<pii,bool> passou;

int main()
{
	int N,M,K;
	std::cin>>N>>M>>K;
	for(int i=0;i!=N;++i){
		std::cin>>chaves[i];
	}
	for(int i=0;i!=M;++i){
		int a,b,c,d;
		std::cin>>a>>b>>c>>d;--a;--b;
		conexoes[{a,d}].push_back({b,c});
		conexoes[{b,d}].push_back({a,c});
	}
	std::priority_queue<pli,std::vector<pli>,std::greater<pli>> queue;
	queue.push({0,{0,chaves[0]}});
	while(queue.size()){
		auto __ = queue.top();
		queue.pop();
		ll custo = __.first;
		int pos = __.second.first;
		int chave = __.second.second;
		if(pos==N-1){///Chegou no final
			std::cout<<custo<<"\n";
			goto prox;
		}
		if(passou[__.second])continue;///Total MlogM
		passou[__.second]=1;
		if(!passa[pos]&&chaves[pos]){///Simula troca de chave
			queue.push({custo,{pos,chaves[pos]}});
		}
		passa[pos]=1;
		for(auto&x:conexoes[__.second]){
			queue.push({custo+(ll)x.second,{x.first,chave}});
		}
	}
	///Impossivel alcancar o final
	std::cout<<"-1\n";
	prox:{}
}