MENU

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

2018 年 09 月 03 日 • 阅读: 1833 • 图论阅读设置

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。

代码

判题状态提交时间运行时间运行内存
正确通过2018-09-03 16:08204ms18488kB
#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 星期一
最后编辑于: 2020 年 07 月 01 日