# ACM-ICPC 2018 南京赛区网络预赛L. Magical Girl Haze（分层图最短路）

## Magical Girl Haze

There are N cities in the country, and M directional roads from u to v(1≤u,v≤n). Every road has a distance ci. Haze is a Magical Girl that lives in City 1, she can choose no more than K roads and make their distances become 0. Now she wants to go to City N, please help her calculate the minimum distance.

### Input

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

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

Then the following M lines each line has three integers, describe a road, Ui,Vi,Ci. There might be multiple edges between u and v.

It is guaranteed that $N≤100000,M≤200000,K≤10,0≤C_i≤1e^9$. There is at least one path between City 1 and City N.

### Output

For each test case, print the minimum distance.

#### 样例输入

1
5 6 1
1 2 2
1 3 4
2 4 3
3 4 1
3 5 6
4 5 2

#### 样例输出

3

#### 题目来源

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

### 链接

https://nanti.jisuanke.com/t/31001

### 题意

n个点m条有向边，可以让其中不超过k条边的边权为0，问从1到n的最短路径。

### 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 100010;
ll dist[maxn][12]; // dist[i][j]表示到达第i个结点时已经让j条边边权为0
bool vis[maxn][12];
int n, m, k;

struct Node
{
int v, cnt;
ll c;
Node (int _v, ll _c, int _cnt): v(_v), c(_c), cnt(_cnt) {}
bool operator < (const Node & r) const
{
return c > r.c;
}
};

struct Edge
{
int to, cost;
Edge (int _to, int _cost): to(_to), cost(_cost) {}
};

vector <Edge> edge[maxn];

void addedge(int u, int v, int w)
{
edge[u].push_back(Edge(v, w));
}

ll dijkstra(int s, int t, int k)
{
for (int i = 0; i <= n; ++i) // 初始化
for (int j = 0; j <= k; ++j)
{
dist[i][j] = inf;
vis[i][j] = false;
}
priority_queue <Node> Q;
dist[s][0] = 0;
Q.push(Node(s, dist[s][0], 0));
while (!Q.empty())
{
Node tmp = Q.top();
Q.pop();
int u = tmp.v, cnt = tmp.cnt;
if (u == t) // 到达t，返回
return tmp.c;
if (vis[u][cnt])
continue;
vis[u][cnt] = true;
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i].to, cost = edge[u][i].cost;
if (!vis[v][cnt] && dist[u][cnt] + cost < dist[v][cnt]) // 当前边权不为0，状态更新
{
dist[v][cnt] = dist[u][cnt] + cost;
Q.push(Node(v, dist[v][cnt], cnt));
}
if (cnt + 1 <= k && !vis[v][cnt + 1] && dist[u][cnt] < dist[v][cnt + 1]) // 当前边权为0，状态更新
{
dist[v][cnt + 1] = dist[u][cnt];
Q.push(Node(v, dist[v][cnt + 1], cnt + 1));
}
}
}
return -1;
}

int main()
{
int T, u, v, w;
scanf("%d", &T);
while (T--)
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
}
ll ans = inf;
for (int i = 0; i <= k; ++i) // 0 到 k
ans = min(ans, dijkstra(1, n, i));
printf("%d\n", ans);
for (int i = 0; i <= m; ++i)
edge[i].clear();
}
return 0;
}

The end.
2018-09-03 星期一