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;
}