文章目录

• 2022杭电中超杯(1)个人题解
• • 1008 Path
  • • 题意
    • 题目分析与思路
    • AC代码

2022杭电中超杯(1)个人题解

1008 Path

算法知识点：最短路，分层图

题意

nnn个点mmm条边 每条边有权值www 。边的类型分为普通边和特殊边。对于特殊边来说 经过这条边后 可以使用魔法传送到任意点去，若传送的目标点与该点直接相连的，花费为wi−kwi - kwi−k （保证不小于0），否则花费为000。

题目分析与思路

赛时没做出来，赛后看题解是分层图还用普通最短路wa了一发，先分析用普通最短路写的思路与错误，然后分析正解分层图。
看到题目并没有直接想到分层图而是对边分情况讨论直接跑最短路
1.对于普通边，直接跑最短路松弛。
2.对于特殊边，记录一下该点是否由特殊边而来，对于直接与该点相连的点w=w−kw = w - kw=w−k同样松弛即可。对于没有直接相连的点，全图大部分点都是我们的目标，我们可以STL set 维护所有点，使用花费为0的传送直接从uuu到达vvv 因为花费为000 vvv是从当前与源点最近的点uuu松弛而来，之后所有的点dis[x]dis[x]dis[x] 都不可能小于dis[v]=dis[u]dis[v] = dis[u]dis[v]=dis[u] ,于是我们直接将点vvv从set中删除即可，不需要重复遍历。

贴一下错误代码提供参考：不做注释，而之后的正解代码会有详细注释

#include <set>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const ll inf = 1e16;
int n,m,sta,k;
struct node
{int u,t;ll w;bool operator < (const node & A)const {return w > A.w;}
};
ll dis[N];
bool vis[N],st[N];
set<int>s;
vector<node>g[N];
priority_queue<node>q;
void djs()
{s.clear();q.push({sta , 0 , 0});for(int i=1;i<=n;i++){dis[i] = inf;vis[i] = 0;if(i != sta) s.insert(i);}dis[sta] = 0;while(!q.empty()){node p = q.top();q.pop();int u = p.u , t = p.t;if(vis[u]) continue;vis[u] = 1;if(t == 1){for(node e : g[u]){int v = e.u;st[v] = 1;ll w = max(1ll * 0 , e.w - k);if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;q.push({v , 0 , dis[v]});}}vector <int> tmp;for(int v : s){	if(!st[v] && dis[v] > dis[u]){tmp.push_back(v);dis[v] = dis[u];q.push({v , 0 , dis[v]});}st[v] = 0;}for(int v : tmp) s.erase(v);}else{for(node e : g[u]){int v = e.u;ll w = e.w;if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;q.push({v , e.t , dis[v]});}}}}
}
void solve()
{scanf("%d%d%d%d",&n,&m,&sta,&k);for(int i=1;i<=n;i++)  g[i].clear(); for(int i=1;i<=m;i++){int u,v,w,t;scanf("%d%d%d%d",&u,&v,&w,&t);g[u].push_back({v,t,w});}djs();for(int i=1;i<=n;i++) {printf("%lld ",dis[i] < inf ? dis[i] : -1);}puts("");
}
int main()
{int T;scanf("%d",&T);while(T--)solve();return 0;
}

这样的写法是可以过题目的样例的，莽一发后再次沉思为什么一定要用分层图，要用dis[i][0/1],vis[i][0/1]dis[i][0/1] ,vis[i][0/1]dis[i][0/1],vis[i][0/1]来代表从特殊边/普通边而来的距离和标记，直接分类讨论优先队列里记录从那种边而来不行吗。于是想到以下的问题：

dis[i][0] 代表普通边的图 1代表特殊边的图
为什么分层图？ 若把经过普通边和特殊边的图放在一起存储 那么会发生如下的错误
数据：
4 3 1 1
1 2 3 1 1->2 花费3 且为特殊边
1 3 1 0 1->3 花费1 普通边
3 2 1 0 3->2 花费1 普通边

我们可以看出 若想到点4 必须经过1->2的特殊边后 经过传送到达4 dis[4]=3dis[4] = 3dis[4]=3

但实际上跑普通最短路不对图分层会出现bug 我们来模拟一下上面的数据：
优先队列中的变量[u,type,dis][u,type,dis][u,type,dis] 分别代表点的编号，从哪一种而来，与源点的距离

1.通过边1->2松弛点2 dis[2]=3dis[2] = 3dis[2]=3 点(2,1,3)加入优先队列
2.通过边1->3松弛点3 dis[3]=1dis[3] = 1dis[3]=1 点(3,0,1)加入优先队列 点1的松弛结束
3.队列中点3的dis更小 将点3取出队列来松弛其他点 发现点2可以继续松弛 dis[2]=dis[3]+1=2dis[2] = dis[3] + 1 = 2dis[2]=dis[3]+1=2将(2,0,2)加入优先队列
4.将点(2,0,2)取出队列发现没有能松弛的点
5.将点(2,1,3)取出队列
bug1 因为djs每次取出队列的元素会进行标记 点2已经在第4步被标记过了 vis[2] = 1 continue 点4未被遍历到 输出不能到达 显然错误
bug2 将代码改进一下 标记数组多一维对是否来自特殊边标记 vis[2][0]=1vis[2][1]=0vis[2][0] = 1 vis[2][1] = 0vis[2][0]=1vis[2][1]=0 ,那么此时(2,1,3)可以继续松弛
但是松弛时我们用的dis不是从队列里取出来的那一个 而是dis数组中的被松弛过的dis[2] 那么dis[4] = dis[2] = 2 显然也是错误
那么只能dis数组也多开一维记录了，这个做法就是分层图的思想

AC代码

#include <set>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const ll inf = 1e16;
int n,m,sta,k;
struct node
{int u,ty;ll w;bool operator < (const node & A)const {return w > A.w;}
};
int st[N];//对当前点的邻接点染色
ll dis[N][2];
bool vis[N][2];//标记set<int>s;//存的是图中所有点集
vector<node>g[N];
priority_queue<node>q;
void djs()
{q.push({sta , 0 , 0});for(int i=1;i<=n;i++){dis[i][0] = dis[i][1] = inf;   vis[i][0] = vis[i][1] = 0;if(i != sta) s.insert(i); //起点已经是最短的当然不用入队}dis[sta][0] = 0;int color = 0;while(!q.empty()){node p = q.top(); q.pop();int u = p.u , ty = p.ty;if(vis[u][ty]) continue ;vis[u][ty] = 1;s.erase(u);color ++; // 对该点的邻接点染色 的颜色if(ty == 1){for(node e : g[u]) st[e.u] = color;vector <int> tmp ;for(int v : s){if(st[v] != color) tmp.push_back(v); //将非邻接点存入临时vec}for(int v : tmp){//tmp中全是非邻接点可以花费代价为0进行传送s.erase(v); // dis[v] = dis[u] 已经等于离起点最接近的点直接erasedis[v][0] = dis[u][ty];q.push({v , 0 , dis[v][0]});}} ll base = ty == 0 ? 0 : k;// 是特殊边可以减免花费 for(node e : g[u]){int v = e.u;ll w = e.w - base;if(dis[v][e.ty] > dis[u][ty] + w){dis[v][e.ty] = dis[u][ty] + w;q.push({v , e.ty , dis[v][e.ty]});//就算是传送到达的点v 如果ty = 1 也被认为是经过了特殊边}}}
}
void solve()
{scanf("%d%d%d%d",&n,&m,&sta,&k);for(int i=1;i<=n;i++){g[i].clear();  st[i] = 0;}for(int i=1;i<=m;i++){int u,v,w,t;scanf("%d%d%d%d",&u,&v,&w,&t);g[u].push_back({v,t,w});}djs();for(int i=1;i<=n;i++) {ll dist = min(dis[i][0] , dis[i][1]);printf("%lld ",dist < inf ? dist : -1);}puts("");
}
int main()
{int T;scanf("%d",&T);while(T--)solve();return 0;
}

其他题目也会陆续更新。

更新：
7.27 1008 path