C++(g++ 7.5.0) 解法, 执行用时: 31ms, 内存消耗: 1508K, 提交时间: 2023-05-24 15:02:49

#include <bits/stdc++.h>

using i64 = std::int64_t;

constexpr i64 inf = ~0uLL >> 1;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n, m, k;
	std::cin >> n >> m >> k;

	std::vector<int> a(n);
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
	}

	std::vector<std::vector<std::pair<int, int>>> adj(n);
	for (int i = 0; i < m; i++) {
		int x, y, z;
		std::cin >> x >> y >> z;
		x--, y--;	
		adj[x].emplace_back(y, z);
		adj[y].emplace_back(x, z);
	}

	std::map<std::pair<int, int>, int> vis;
	std::priority_queue<std::tuple<i64, int, int>> q;

	q.emplace(0, 0, 0);

	std::vector<i64> dist(n, inf);

	while (!q.empty()) {
		auto [d, x, cur] = q.top();
		q.pop();
		if (vis[{x, cur}]) continue;
		vis[{x, cur}] = true;
		dist[x] = std::min(dist[x], -d);

		for (auto [y, dis] : adj[x]) {
			if (vis[{y, cur + a[x]}] || cur + a[x] > k) continue;
			q.emplace(d - dis, y, cur + a[x]);
		}
	}

	std::cout << (dist[n - 1] == inf ? -1 : dist[n - 1]) << "\n";

	return 0;
}

C++14(g++5.4) 解法, 执行用时: 291ms, 内存消耗: 688K, 提交时间: 2019-11-28 21:40:33

#include<bits/stdc++.h>
using namespace std;

int i,j,w,n,m,k,V[805];
vector<int>R[805],W[805];
bool U[805];
void DFS(int x,int h,int c)
{
	int i,j,C=c+U[x];
	if(C>k)return;
	for(i=0;i<R[x].size();i++)
	{
		j=R[x][i];
		if(V[j]>h+W[x][i])V[j]=h+W[x][i],DFS(j,h+W[x][i],C);
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=n;i++)scanf("%d",&U[i]);
	memset(V,0x3f,sizeof(V));
	while(m--)
	{
		scanf("%d%d%d",&i,&j,&w);
		R[i].push_back(j),W[i].push_back(w);
		R[j].push_back(i),W[j].push_back(w);
	}
	V[1]=0,DFS(1,0,0);
	V[n]<1e9?printf("%d\n",V[n]):printf("-1\n");
    return 0;
}