C++(clang++ 11.0.1) 解法, 执行用时: 687ms, 内存消耗: 13852K, 提交时间: 2022-08-26 22:05:45

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,x,y,z,a[N];
long long dis[N];
vector<int>e[N];
queue<int>q;
bool vis[N];
void SPFA(){
	memset(dis,0x3f,sizeof dis);
	dis[1]=0; q.push(1); vis[1]=1;
	while(!q.empty()){
		int u=q.front(); q.pop(); vis[u]=0;
		for(int i=0;i<e[u].size();++i){
			int v=e[u][i],w1,w2;
			if(a[u]==a[v]){
				w1=x;
				w2=z+y;
			} else {
				w1=y;
				w2=z+x;
			}
			if(dis[v]>dis[u]+w1 || dis[v]>dis[u]+w2){
				dis[v]=min(dis[v],dis[u]+min(w1,w2));
				if(!vis[v]){ q.push(v); vis[v]=1; }
			}
		}
	}
}
int main(){
	scanf("%d %d %d %d %d",&n,&m,&x,&y,&z);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1;i<=m;++i){
		int u,v;
		scanf("%d %d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	SPFA();
	printf("%lld",dis[n]);
	return 0;
}

pypy3 解法, 执行用时: 1612ms, 内存消耗: 61060K, 提交时间: 2022-08-26 20:45:57

from queue import deque
import heapq
n, m = map(int, input().split())
x, y, z = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + a
ed = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = map(int, input().split())
    ed[u].append(v)
    ed[v].append(u)
q = [(0, 1)]
#vst = dict()
#vst[1] = 0
ans = [float("inf")] * (n + 1)
ans[1] = 0
while q:
    tp = heapq.heappop(q)
    #print(tp)
    for e in ed[tp[1]]:
        #if not x in vst:
        np = (tp[0] + (min(x, y + z) if a[e] == a[tp[1]] else min(y, x + z)), e)
        if np[0] < ans[e]:
            heapq.heappush(q, np) 
            ans[e] = np[0]
    #print(q)
print(ans[n])