B.矿井寻踪(trace)
题目描述
丰富的美食让你们心满意足,肚子饱饱的你准备下井探矿,寻找星露谷失落的珍宝。
每个矿井间通过错综复杂的隧道连接,而且还受到结界的影响。具体而言,矿井和隧道呈现为一张有向带权图,其中权值是通过该隧道的时间。由于里面时常有怪物出没,经过前人的探索,每条隧道被设立了魔法结界,为了保障安全都只有一个方向是可以通过,即这是一张有向图。
不过森林的魔法波动让隧道结界发生了变化。第 000 天,隧道没有变化,而在第 1∼m1 \sim m1∼m 天的凌晨,若第 iii 天的波动值 pip_ipi 为 111,则第 iii 条隧道的结界方向会发生变化,直至午夜时恢复原结界方向,即这条边会反向,一天后恢复。若 pip_ipi 为 000 则表示该隧道结界足够强大,未受到波动影响。
假设起点在矿井 S=1S=1S=1 号矿井,珍宝的位置在矿井 T=2T=2T=2 号矿井,你想知道如果你中午进入起点,从 SSS 到达 TTT 的最短时间相比于魔法波动前(即相比于第 000 天),会变大、变小还是不变?保证第 000 天两者连通。
输入格式
第一行输入两个数 n,mn,mn,m,表示矿井和隧道的数量;
接下来输入一行一个长度为 mmm 的字符串 ppp,其中 pip_ipi 表示第 iii 天隧道 iii 是否受到波动影响。
最后 mmm 行每行输入三个数 ui,vi,wi (1≤ui,vi≤n, 1≤wi≤105)u_i,v_i,w_i\ (1 \le u_i,v_i \le n,\ 1 \le w_i \le 10^5)ui,vi,wi (1≤ui,vi≤n, 1≤wi≤105),表示这条隧道的起点、终点和通过时间。
输出格式
第一行先输出第 000 天从起点到珍宝的最短时间。
接下来 2∼m+12 \sim m+12∼m+1 行:
- 若今天从起点到珍宝的最短时间变小了,输出
HAPPY; - 若今天从起点到珍宝的最短时间变大了,输出
SAD; - 若今天从起点到珍宝的最短时间未变,输出
SOSO。
样例1输入
4 5
11111
1 3 5
3 4 6
4 2 7
2 1 18
2 3 12
样例1输出
18
SAD
SAD
SAD
SOSO
HAPPY
样例2输入
7 5
11111
1 3 2
1 6 3
4 2 4
6 2 5
7 5 6
样例2输出
8
SOSO
SAD
SOSO
SAD
SOSO
样例3输入
10 14
11111111111111
1 7 9
1 8 3
2 8 4
2 6 11
3 7 8
3 4 4
3 2 1
3 2 7
4 8 4
5 6 11
5 8 12
6 10 6
7 10 8
8 3 6
样例3输出
10
SOSO
SAD
HAPPY
SOSO
SOSO
SOSO
SAD
SOSO
SOSO
SOSO
SOSO
SOSO
SOSO
SAD
对于所有数据,保证 2≤n≤105, 1≤m≤105, 1≤ui,vi≤n, 1≤wi≤105, pi∈{0,1}2 \le n \le 10^5,\ 1 \le m \le 10^5,\ 1 \le u_i,v_i \le n,\ 1 \le w_i \le 10^5,\ p_i \in \{0,1\}2≤n≤105, 1≤m≤105, 1≤ui,vi≤n, 1≤wi≤105, pi∈{0,1}。保证第 000 天 S,TS,TS,T 连通,保证没有重边和自环。
题解
提供一种最短路图上dp计数的方法,直接边跑边做就好了,没必要单独存出来一个图再拓扑。
对于乘法会炸提供一种双模数hash的解决方法。
题目要O(1)求将有向图中每条边反向后,从S->T的最短路长度变化情况。
显然如果新加入的边会有用,当且仅当加入后新图S->T中所有最短路都必须经过新边。
具体地,设原用时为dis(1,2),若反转边(u,v,w)则新用时为dis(1,v)+w+dis(u,2)
然后分讨大小关系:
原用时<新用时 -- HAPPY
原用时=新用时 -- SOSO
原用时>新用时:
发现当且仅当所有的原最短路径都经过这条边时,耗时更久
意思是它在当前所有最短路的“主干道”上,它一旦反向就会让原来所有的最短路“跑不通”,肯定会更劣
考虑如何判断,注意到如果把只在最短路上的边拿出来形成的“最短路图”是一个DAG,所以可以正反跑拓扑记录到每个点的最短路条数
则经过一条边(u,v)的最短路条数为cntS[u]*cntT[v],判断它是否等于原来总的最短路条数即可判断这种情况
但是总的最短路条数只要构造一个边权都相等的菱形图就可以卡到2^n次方级别,为了避免乘法溢出可以用双模数hash,出错概率比较低
(如果满足条件hash一定是对的,会出错当且仅当P1*P2能整除cntS[u]*cntT[v],但概率很小)
注:最好的方法是把最短路图看成无向,然后Tarjan求割边,一条边在“主干道”上等价于它是最短路图上的割边
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7,P1=998244353,P2=1e9+7;
int n,m; string p;
struct Node{
ll d; int u;
bool operator<(Node p)const{
return d>p.d;
}
};
ll c1[3][N],c2[3][N];
void dij(int s,vector<array<ll,2>> (&G)[N],vector<ll> &dis){
for(int i=0;i<=n;i++) dis[i]=1e18;
vector<int> vis(n+1);
priority_queue<Node> Q; Q.push({0,s}); dis[s]=0;
c1[s][s]=c2[s][s]=1;
while(!Q.empty()){
int u=Q.top().u; Q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto it:G[u]){
int v=it[0]; ll w=it[1];
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w; Q.push({dis[v],v});
c1[s][v]=c1[s][u],c2[s][v]=c2[s][u];
}else if(dis[v]==dis[u]+w){
c1[s][v]=(c1[s][v]+c1[s][u])%P1,c2[s][v]=(c2[s][v]+c2[s][u])%P2;
}
}
}
}
vector<array<ll,2>> G[N],rG[N]; //正图、反图
int u[N],v[N],w[N];
void solve()
{
cin>>n>>m>>p;
for(int i=1;i<=m;i++){
cin>>u[i]>>v[i]>>w[i];
G[u[i]].push_back({v[i],w[i]}); rG[v[i]].push_back({u[i],w[i]});
}
vector<ll> ds(n+1,1e18),dt(n+1,1e18);
dij(1,G,ds); dij(2,rG,dt);
cout<<ds[2]<<'\n';
for(int i=1;i<=m;i++){
if(p[i-1]=='0'){
cout<<"SOSO\n"; continue;
}
ll tim=ds[v[i]]+w[i]+dt[u[i]]; //新用时
if(tim<ds[2]) cout<<"HAPPY\n";
else if(tim==ds[2]) cout<<"SOSO\n";
else{
//在原来的最短路上且方案数相等,所以是必经之路
if(ds[u[i]]+w[i]+dt[v[i]]==ds[2] &&
c1[1][u[i]]*c1[2][v[i]]%P1==c1[1][2]%P1 &&
c2[1][u[i]]*c2[2][v[i]]%P2==c2[1][2]%P2){
cout<<"SAD\n";
}else{
cout<<"SOSO\n";
}
}
}
}
signed main()
{
freopen("trace.in","r",stdin);
freopen("trace.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
solve();
return 0;
}
转载自 CSDN-专业IT技术社区




