思路：

一道最短路的题。。。

分层最短路的板子。。。

对于图中的所有节点



u

u






u





，他可以拆成



k

+

1

k + 1






k




+








1





个节点



u

j

u_j







u










j





​















，而且j



∈

\in






∈





[0,k]。

分别表示当使用



j

j






j





次免费通行权限后到达



u

u






u





号节点的状态。

对于，样例来说那个图的话（脑补）

加工中

。

list[i][j]为到达i用了j次免费机会的最小花费。

vis[i][j]为到达i用了j次免费机会的情况是否出现过。

对于某些路径，我们可以选择使用机会，也可以选择不使用机会。

之后就分两种情况 ：

void spfa() {
    int head = 1;
	int tail = 2;
    memset(list, 0 ,sizeof(list));
    list[1][0] = ks;
	list[1][1] = 0;
    while(head != tail) {
        int x = list[head][0];
		int c = list[head][1];
        for(int k = last[x];k;k = a[k].next) {
            int y = a[k].y;
            if(f[x][c] + a[k].dis < f[y][c]) {
                f[y][c] = f[x][c] + a[k].dis;
                if(vis[y][c] == false) {
                    vis[y][c] = true;
                    list[tail][0] = y;
                    list[tail][1] = c;
                    tail ++;
					if(tail == a_b) {
						tail = 1;
					}
                }
            }
            if(f[x][c] < f[y][c + 1] && c < d_k) {
                f[y][c + 1] = f[x][c];
                if(vis[y][c + 1] == false) {
                    vis[y][c + 1] = true;
                    list[tail][0] = y;
                    list[tail][1] = c + 1;
                    tail ++;
					if(tail == a_b){
						tail = 1;
					}
                }
            }
        }
        head ++;
		if(head == a_b) {
			head = 1;
		}
        vis[x][c] = false;
    }
}