Revamping Trails 道路升级——多维最短路

题目：

描述

每天,农夫John需要经过一些道路去检查牛棚N里面的牛. 农场上有M(1<=M<=50,000)条双向泥土道路,编号为1…M.

道路i连接牛棚P1_i和P2_i (1 <= P1_i <= N; 1 <= P2_i<= N). John需要T_i (1 <= T_i <= 1,000,000)时间单位

用道路i从P1_i走到P2_i或者从P2_i 走到P１_i 他想更新一些路经来减少每天花在路上的时间.具体地说,他想更新

K (1 <= K <= 20)条路经，将它们所须时间减为０．帮助FJ选择哪些路经需要更新使得从１到N的时间尽量少.

输入

• 第一行: 三个空格分开的数: N, M, 和 K
• 第2…M+1行: 第i+1行有三个空格分开的数：P1_i, P2_i, 和 T_i

输出

• 第一行: 更新最多Ｋ条路经后的最短路经长度．

样例

输入

4 4 1

1 2 10

2 4 10

1 3 1

3 4 100

输出

1

提示

//K是1; 更新道路3->4使得从３到４的时间由１００减少到０. 最新最短路经是1->3->4,总用时为１单位. N<=10000

这道题在一般的最短路上添加了一个可以将k条路变为0消耗的题，原来的dist数组久存不了了，我们现在就开始模拟DP的思想给dist多加一维，使 d i s t [ i ] [ j ] dist[i][j] dist[i][j]表示为从起始点到i用了k次清零的最短路径长度，只需要在计算状态时多判断一下如果清零的状态，主要思路就直接对优化迪杰斯特拉即可。

代码：

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

struct node {
	int k,dis,x;//k表示清零次数，dis表示最短路，x表示当前走到的点 
	node (int a,int b,int c) {
		x=a;
		k=b;
		dis=c;
	}//构造函数 

} ;

bool operator < (node a,node b){
	return a.dis>b.dis;
}//堆优化需对结构体进行判断，因为堆里装的是结构体，必须重载运算符来排序 

int n,m,k,dst[10001][25],vis[10010][21],nxt[10010],to[100010],head[100010],edg[100010],tot;

void add(int x,int y,int z) {
	tot++;
	nxt[tot]=head[x];
	to[tot]=y;
	edg[tot]=z;
	head[x]=tot;
}//前向星存储 

void dij(int s) {
	memset(dst,0x3f3f3f,sizeof(dst));

	priority_queue<node>q;//堆优化大法好！ 
	dst[s][0]=0;//起始点到自己的最短路为0 

	q.push(node(s,0,0));
	while(!q.empty()) {
		node now=q.top();
		q.pop();
		int u=now.x;
		int ti=now.k;
		if(vis[u][ti]) {
			continue;
		}//访问过就退出 
		vis[u][ti]=1;
		for(int i=head[u]; i; i=nxt[i]) {
			int v=to[i];
			if(dst[v][ti]>dst[u][ti]+edg[i]) {
				dst[v][ti]=dst[u][ti]+edg[i];
				q.push(node(v,ti,dst[v][ti]));
			}//没用的情况 
			if(ti+1<=k&&dst[v][ti+1]>dst[u][ti]) {
				dst[v][ti+1]=dst[u][ti];
				q.push(node(v,ti+1,dst[v][ti+1]));
			}//用了清零的情况 
		}

	}

}

int main() {




//		memset(vis,0,sizeof(vis));
//		memset(head,0,sizeof(head));
//		memset(to,0,sizeof(to));
//		memset(nxt,0,sizeof(nxt));
//		memset(edg,0,sizeof(edg));
//		memset(e,0,sizeof(e)); 
//	tot=0;
	cin>>n>>m>>k;
	for(int i=1; i<=m; i++) {
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	dij(1);//从1开始为起点 
	cout<<dst[n][k]; //走到n，用了k次的最短路 



	    return 0;
}