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的最短路径。

题解

据说叫“分层图最短路”，其实就是把一个点拆成多个状态，有一点dp的感觉，和UVA11367 Full Tank?这道题类似。

使用堆优化的dijkstra，结点记录三个信息：v代表标号，c代表s到该店的最短路，cnt代表到达该点时边权已经为0的数量；dist变成二维的，$dist[i][j]$表示到达第i个结点时已经让j条边边权为0，然后对于当前结点u，与u连边的结点v，我们要更新两种状态，一种是uv结点的连边边权不为0，一种是uv结点的连边边权为0（需要判断$cnt<=k$），然后就可以得到答案了。

注意，需要使用long long。

代码

#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);
            addedge(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;
}

补题，补题。好像是BZOJ原题：传送门，还有另外一种做法，最开始加边的时候就直接拆点连边，但是可能时间会爆炸。

The end.
2018-09-03 星期一