记录编号	330298	评测结果	AAAAAAAAAA
题目名称	智爷的传送门	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.782 s
提交时间	2016-10-26 14:45:34	内存使用	2.29 MiB

#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
using namespace std;

const int edgenum = 50010, nodenum = 10010;
int n, m, k;
struct Edge
{
	int to, w, next;
}edges[edgenum << 1];
int head[nodenum], tot;
int dis[nodenum][21];
struct Node
{
	int pos, tot, last;
	inline Node(const int& a, const int& b, const int& c) { pos = a; tot = b; last = c; }
	inline bool operator < (const Node& a) const { return tot > a.tot; }
};
priority_queue <Node> Q;

inline void Read(int& a)
{
	a = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') {
		a = a * 10 + ch - '0';
		ch = getchar();
	}
}

inline void AddEdge(const int& from, const int& to, const int& w)
{
	edges[++tot].to = to;
	edges[tot].w = w;
	edges[tot].next = head[from];
	head[from] = tot;
}

inline void Dijkstra(const int& s, const int& t)
{
	memset(dis, 0x3f, sizeof dis);
	dis[s][k] = 0;
	Q.push(Node(s, 0, k));
	while (!Q.empty()) {
		Node top = Q.top(); Q.pop();
		int pos = top.pos, tot = top.tot, last = top.last;
		if (tot != dis[pos][last]) continue;
		for (int i = head[pos]; i; i = edges[i].next) {
			int to = edges[i].to, w = edges[i].w;
			if (dis[to][last] > dis[pos][last] + w) {
				dis[to][last] = dis[pos][last] + w;
				Q.push(Node(to, dis[to][last], last));
			}
			if (last) {
				if (dis[to][last-1] > dis[pos][last]) {
					dis[to][last-1] = dis[pos][last];
					Q.push(Node(to, dis[to][last-1], last-1));
				}	
			}
		}
	}
	int ans = 0x7f7f7f7f;
	for (int i = 0; i <= k; ++i)
		ans = min(ans, dis[t][i]);
	printf("%d\n", ans);
}

#define SUBMIT
int main()
{
#ifdef SUBMIT
	freopen("doors.in", "r", stdin); freopen("doors.out", "w", stdout);
#endif

	Read(n); Read(m); Read(k);
	int from, to, w;
	for (int i = 1; i <= m; ++i) {
		Read(from); Read(to); Read(w);
		AddEdge(from, to, w);
		AddEdge(to, from, w);
	}
	
	Dijkstra(1, n);

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#endif

	return 0;
}