[分层最短路]Magical Girl Haze

问题描述

一张图，共有m条路，从1走到n，一共可以使k条路的路程为0，求最短路。

思路

去掉的k条路肯定全部在从1到n的某一条路径上，这样走这一条路径才有可能最短。我们可以对最短路分层，即分别求k为0，k为1，k为2……k为k的情况下最短路程。定义最短路时使用二维数组dis[n][k],n为结点数，k为分层数。设i为每次求得的最短路结点，kk为所在层，dis为最短路，原点到原点的距离为0，则：

最短路状态转移方程：dis[j][kk]=min(dis[i][kk]+road[i][j],dis[j][kk])

分层状态转移方程：dis[j][kk+1]=min(dis[i][kk],dis[j][kk+1])

Magical Girl Haze

There are NN cities in the country, and MMdirectional roads from uu to v(1\le u, v\le n)v(1≤u,v≤n). Every road has a distance c_ici. Haze is a Magical Girl that lives in City 11, she can choose no more than KK roads and make their distances become 00. Now she wants to go to City NN, please help her calculate the minimum distance.

Input

The first line has one integer T(1 \le T\le 5)T(1≤T≤5), then following TT cases.

For each test case, the first line has three integers N, MN,M and KK.

Then the following MM lines each line has three integers, describe a road, U_i, V_i, C_iUi,Vi,Ci. There might be multiple edges between uu and vv.

It is guaranteed that N \le 100000, M \le 200000, K \le 10N≤100000,M≤200000,K≤10,
0 \le C_i \le 1e90≤Ci≤1e9. There is at least one path between City 11 and City NN.

Output

For each test case, print the minimum distance.

样例输入复制

样例输出复制

题目来源

ACM-ICPC 2018 南京赛区网络预赛

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxx = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5+7;
int t,n,m,k,cnt;
ll dis[maxn][12];
bool vis[maxn][12];
int head[maxn];
struct EDGE{
    int next;
    int to;
    ll w;
}edge[2*maxn];
struct NODE{
    int u, j;
    ll dis;
    NODE(){}
	NODE(int u,int j,ll w):u(u),j(j),dis(w){}
	bool operator <(const NODE &a)const
	{
		return dis>a.dis;
	}
}node[2*maxn];
void add(int u, int v, ll w){
    edge[cnt].next = head[u];
    edge[cnt].to = v;
    edge[cnt].w = w;
    head[u] = cnt;
    cnt++;
}
void dijkstra(int s){
    memset(dis,maxx,sizeof(dis));
    memset(vis,false,sizeof(vis));
    priority_queue<NODE>q;
    q.push(NODE(s,0,0));
    while(!q.empty()){
        int kk = q.top().u;
        int j = q.top().j;
        ll minD = q.top().dis;
        q.pop();
        if(vis[kk][j])
            continue;
        vis[kk][j] = true;
        for(int l = head[kk]; l!=-1; l=edge[l].next){
            if(j<k&&!vis[edge[l].to][j+1]&&dis[edge[l].to][j+1] > minD){
                dis[edge[l].to][j+1] = minD;
                q.push(NODE(edge[l].to,j+1,dis[edge[l].to][j+1]));
            }
            if(!vis[edge[l].to][j]&&minD + edge[l].w < dis[edge[l].to][j]){
                dis[edge[l].to][j] = minD + edge[l].w;
                q.push(NODE(edge[l].to,j,dis[edge[l].to][j]));
            }
        }
    }
}
int main(){
    ll u,v,w;
    scanf("%d",&t);
    while(t--){
        memset(head,-1,sizeof(head));
        cnt = 0;
        scanf("%d%d%d",&n,&m,&k);
        for(int i = 0;i < m; i++){
            scanf("%d%d%lld",&u,&v,&w);
            add(u,v,w);
        }
        dijkstra(1);
        if(dis[n][k]!=maxx)
        	printf("%lld\n",dis[n][k]);
        else
            printf("0\n");
    }
    return 0;
}