C++11(clang++ 3.9) 解法, 执行用时: 1127ms, 内存消耗: 30688K, 提交时间: 2019-05-11 16:09:24

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int maxn = 2e5;
constexpr int maxk = 7;
vector<pair<int, LL> > G[maxn];
LL d[maxn * maxk];
bool done[maxn * maxk];
priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>> q;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 1; i <= m; i += 1){
		int a, b, c;
		cin >> a >> b >> c;
		a -= 1, b -= 1;
		G[a].push_back(make_pair(b, c));
		G[b].push_back(make_pair(a, c));
	}
	fill(d, d + maxn * maxk, 1e18);
	q.push({d[0] = 0, 0});
	while(not q.empty()){
		int u = q.top().second;
		q.pop();
		if(done[u]) continue;
		done[u] = true;
		for(const auto &p : G[u % n]){
			int v = p.first + u / n * n, w = p.second;
			if(d[v] > d[u] + w) q.push({d[v] = d[u] + w, v}); 
		}
		if(u / n < k) for(const auto &p : G[u % n]){
			int v = p.first + u / n * n + n;
			if(d[v] > d[u] + 1) q.push({d[v] = d[u] + 1, v}); 
		}
	}
	LL ans = 1e18;
	for(int j = 0; j <= k; j += 1)
		ans = min(ans, d[j * n + n - 1]);
	cout << ans;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 527ms, 内存消耗: 49204K, 提交时间: 2019-11-10 16:39:18

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
#define ll long long 
int n,m,k;
struct node 
{
	int v,w;
};
vector<node>G[N];
struct node1
{
	int v,k;
	ll w; 
	bool operator<(const node1&p) const
	{
		return w>p.w;
	};
} ;
ll d[N][10];
ll dfs()
{
	priority_queue<node1>q;
	while(q.size())q.pop();
	for(int i=1;i<=n;i++) for(int j=0;j<=k;j++) d[i][j]=0x3f3f3f3f3f3f3f3f;
	q.push({1,0,0});
	d[1][0]=0;
	while(q.size())
	{
		node1 t=q.top();
		q.pop();
		int u=t.v;
		if(t.v==n) return t.w;
		for(int i=0;i<G[u].size();i++)
		{
			int v=G[u][i].v;
			int w=G[u][i].w;
			if(d[v][t.k]>d[u][t.k]+w)
			{
				d[v][t.k]=d[u][t.k]+w;
				q.push({v,t.k,d[v][t.k]});
			}
			if(t.k+1<=k)
			{
				if(d[v][t.k+1]>d[u][t.k]+1)
				{
					d[v][t.k+1]=d[u][t.k]+1;
					q.push({v,t.k+1,d[v][t.k+1]});
				}
			}
		}
	} 
}
int main()
{
	
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		G[x].push_back({y,w});
		G[y].push_back({x,w});
	}
	cout<<dfs()<<endl;
	return 0;
}