ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze
简要说下题意:
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
在没有分层前
这样求1-4的最短路径直接dijk,但现在你可以将2条边置位0,当然把2--3 变为0,3--4变为0,这样从1--4的最短路径长度就是3
因为我们不知道要具体改变哪一条边。所以我们要在在所有边的基础上增加一个长度为0的距离
分层后
蓝色部分为增加的距离为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次
看上面代码,这时候有个问题,我每次只判断了当前层和上一层,其他层呢?
这个到没关系,每次判断了上一层我把上一层的信息也压入队列,当出队列时会对这个节点的上一层进行判断
我进行次数的k这个数值是要保存到结构体里面,不可设为全局变量(自己思考)
下面的工作就是套dijkstra,然后修改判断条件,较为麻烦的就是结构体的设置
说下结构体变量
这个结构体里面存的边v和距离c,
这样说明a节点有一条边v,距离长度c
d数组保存的时路径的最小值,
node是要压入优先队列中
- u的含义相当于d[i][j]中的i
- 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;
}
要了老命了。。好久没写过这么细的题解了
推荐阅读
-
ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze(队列优化的dijkstra,dp)
-
ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze
-
ACM-ICPC 2018 南京赛区网络预赛 L Magical Girl Haze - 分层最短路
-
ACM-ICPC 2018 南京赛区网络预赛 J Sum - 线性筛+找规律
-
ACM-ICPC 2018 南京赛区网络预赛 C GDY - 模拟
-
L. Poor God Water [ ACM-ICPC 2018 焦作赛区网络预赛 ]
-
ACM-ICPC 2018 焦作赛区网络预赛 L. Poor God Water(杜教)
-
ACM-ICPC 2018 焦作赛区网络预赛 L. Poor God Water(水)