欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze

程序员文章站 2022-06-04 12:46:16
...

题目传送门

 

简要说下题意:

N个城市,有M条边相连,现在可以任意选中k条边把这k条边的长度置位0,然后求从1---N的最短路径

想到最短路径没有负权,基本想到的是Dijkstra。这个算法主要写起来比较方便,spfa一样,个人不喜欢(两个算法昆哥上课讲过,不懂的看PPT)

 

 

 

先看这题。暑期训练的题目,基本上一样,除了比赛那题数据大+多组数据

上学

【题意描述】

小喵喵家附近有n个路口,m条道路连接着这些路口,而且通过这些道路各自需要一些时间c[i]。小喵喵在1号路口,他要去n号路口上学,但是他马上要迟到了,所以他想知道最短需要多长时间能够到达学校。其中忽略小喵喵由于出家门、到n号路口之后进入学校、从一条道路移动到另一条道路之类的时间,只计算他在这些道路上花费的时间总和。

除此之外,小喵喵还有k个时间暂停器,每个可以使某一条道路的经过时间变为0.

【输入格式】

第1行三个整数n,m,k,表示路口个数,道路的数量,时间暂停器的数量。

第2~m+1行每行三个整数u[i],v[i],c[i],表示u[i]和v[i]之间有一条可以双向通行的道路,通过所需时间为c[i]。

【输出格式】

一个整数,表示小喵喵所需的最短时间。

【样例输入输出】

5 6 1

1 2 2

1 3 4

2 4 3

3 4 1

3 5 6

4 5 2    3

【样例解释】

小喵喵选择从1->3->4->5,并且在1->3的道路上使用时间暂停器。

总耗时为0+1+2=3.

【数据范围】

对于20%的数据,n<=5,m<=10.

对于另外20%的数据,k=0.

对于另外30%的数据,k=1.

对于所有的数据,n<=1000,m<=10000,k<=10,c[i]<=109,保证存在从1号路口到n号路口的路径。注意,可能存在两条道路的起点和终点组成的集合相同,也可能存在起点和终点是相同路口的道路。

 

 

根据题意,既然我能把k条边置为0,说明我在任意两条边之间都要设置一个长度为0的边,不能在原有图的基础上增加,这样会覆盖掉原来的路径长度。我们可以把图分成多层,每一层之间有长度为0的边相连,这样避免了修改原图的路径长度。

例如这样一组数据

4 3 2

1 2 3

2 3 4

3 4 5

在没有分层前

ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze

这样求1-4的最短路径直接dijk,但现在你可以将2条边置位0,当然把2--3 变为0,3--4变为0,这样从1--4的最短路径长度就是3

因为我们不知道要具体改变哪一条边。所以我们要在在所有边的基础上增加一个长度为0的距离

分层后

ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze

ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze

蓝色部分为增加的距离为0的路径,注意,这个路径是单项路径,避免在跑回去

这样,然后从第k层使用dijkstra算最短路径。根据建立的图只要达到了n的倍数,说明到达第i层的最后一个点

这样每次判断到达每层的最小值,然后输出

代码没什么要过多叙述的,除了在加边还有判断最后一个节点上,其他和Dijkstra的裸题基本一样

#include <iostream>
#include <queue>
using namespace std;
struct Node{
    long long v, w;
    Node(){}
    Node(long long av, long long aw): v(av), w(aw){}
    bool operator < (const Node& b) const {
        return w > b.w;
    }
}node;
vector<vector<Node>> g;
priority_queue<Node> q;
vector<bool> bUsed;
const long long INF = (long long)1 << 62;
long long minN = INF, n, m, k, u, v, w;
void Dijkstra() {
    q.push(Node(1+k*n, 0));
    while (q.size()) {
        node = q.top(), q.pop();
        if (bUsed[node.v]) continue;
        bUsed[node.v] = true;
        if (node.v % n == 0) 
            minN = min(minN, node.w);
        for (int i = 0, j = g[node.v].size(); i < j; ++i) {
            Node tN = g[node.v][i];
            if (bUsed[tN.v]) continue;
            q.push(Node(tN.v, node.w+tN.w));
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    g.resize(m*(k+2)); bUsed.reserve(m*(k+2));
    for (int i = 1; i <= m; ++i) {
        cin >> u >> v >> w;
        //使用多层图,将动态规划的各个状态以不同层列出,0边在不同层之间连接,从而避免了重边
        for (int j = 0; j <= k; ++j) {
            g[u+j*n].push_back(Node(v+j*n, w));
            g[v+j*n].push_back(Node(u+j*n, w));
            if (j) {
                g[u+j*n].push_back(Node(v+(j-1)*n, 0));
                g[v+j*n].push_back(Node(u+(j-1)*n, 0));
            }
        }
    }
    Dijkstra();
    cout << minN << endl;
    return 0;
}

 

看比赛的题。。

这题数据贼大,原思想会超时的。需要稍微优化下,还有注意单向!

这个想法还是分层+动态规划+dijk。每次直接计算在第k层节点i的距离,到达一个节点i时 。两种情况

  • 判断加上路径长度后和当前结点所保存的长度比较
  • 判断置位0的情况下和当前节点比较,注意置为0的个数不能超过k次

ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze

看上面代码,这时候有个问题,我每次只判断了当前层和上一层,其他层呢?

这个到没关系,每次判断了上一层我把上一层的信息也压入队列,当出队列时会对这个节点的上一层进行判断

我进行次数的k这个数值是要保存到结构体里面,不可设为全局变量(自己思考)

下面的工作就是套dijkstra,然后修改判断条件,较为麻烦的就是结构体的设置

说下结构体变量

ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze

这个结构体里面存的边v和距离c,ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze

这样说明a节点有一条边v,距离长度c

ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze

d数组保存的时路径的最小值,

node是要压入优先队列中

  • u的含义相当于d[i][j]中的
  • k相当于j,t表示的时当前u,k保存的最小值

 

 

这题只是在原有的基础上用个dp,减少搜索

是在还不懂,看代码。。代码除了变量用的比较乱,其他感觉还行

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int MAXN = 200005;
const long long INF=(long long)1 << 61;
int n, m, k1;
int s, t;
long long d[MAXN][15];
struct node{
    long long u, k, t;
    node() {}
    node(long long u1, long long k1, long long t1){u = u1, k = k1, t = t1;}
    bool operator<(const node &a) const{
        return a.t < t;
    }
};
struct edge{
    long long v, c;
    edge() {}
    edge(long long v1, long long c1){ v = v1, c = c1;}
};
vector<edge> vec[MAXN];
void df(int s)
{
    priority_queue<node> q;
    long long v, c;
    //memset(d, 0x7f, sizeof(d));
    for(int i=0;i<MAXN;i++){
    	for(int j=0;j<15;j++) d[i][j]=INF;
	}
    d[s][0] = 0;
    q.push(node(s, 0, 0));
    while (!q.empty()){
        node k = q.top();
        q.pop();
        for (int i = 0; i < vec[k.u].size(); i++){
            v = vec[k.u][i].v;
            c = vec[k.u][i].c;
            if (d[k.u][k.k]+c<d[v][k.k]){
                d[v][k.k] = d[k.u][k.k] + c;
                q.push(node(v,k.k,d[v][k.k]));
            }
            if (d[k.u][k.k]<d[v][k.k+1]&&k.k+1<=k1){
                d[v][k.k+1] = d[k.u][k.k];
                q.push(node(v, k.k+1,d[v][k.k+1]));
            }
        }
    }
}
int main(){
    int t1;
    scanf("%d", &t1);
    while (t1--){
        scanf("%d%d%d", &n, &m, &k1);
        n++;
        for(int i=0;i<=n;i++)
            vec[i].clear();
        s=1,t=n-1;
        for (int i=1;i<=m;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            vec[a].push_back(edge(b,c));
        }
        df(s);
        long long ans = d[t][0];
        for (int i = 1; i <= k1; i++)
            ans = min(ans, d[t][i]);
        printf("%lld\n", ans);
    }
    return 0;
}

 

 

 

 

 

 


要了老命了。。好久没写过这么细的题解了