对于一些有限制次数的改变图上的边的题目，将原图复制若干份，也就是若干层，每层之间用特殊的边（题目给出的条件）连接起来，然后再跑最短路。
$k$ 条航线，我们便在原图的基础上再建立 $k$ 张子图，共 $k+1$ 张图，题目给出的特殊条件为转换边权使得其为 $0$，所以对于一条边 $(u,v,w)$，我们需要在第 $i、i+1$ 张图之间连一条 $(u_i,v_i+1,0)$ 的边，表示可以用一次机会使得该边边权变为 $0$。图建完后，再跑一边最短路统计答案即可，注意 $k$ 次机会不一定全部用完。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5,K=15;
struct node{
int v,w;
};
vector<node>a[N*K];
int dis[N*K],f[N*K];
int n,m,k,s,t;
struct cmp{
bool operator ()(const node &A,const node &B)
{
return A.w>B.w;
}
};
void dij()
{
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
priority_queue<node,vector<node>,cmp>q;
q.push((node){s,0});
while(!q.empty())
{
node now=q.top();q.pop();
int u=now.v;
if(f[u])continue;
f[u]=1;
for(int i=0;i<a[u].size();i++)
{
int v=a[u][i].v,w=a[u][i].w;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if(!f[v])q.push((node){v,dis[v]});
}
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>k>>s>>t;
s++,t++;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
u++,v++;
for(int j=0;j<=k;j++)
{
int uu=j*n+u,vv=j*n+v;
a[uu].push_back((node){vv,w});
a[vv].push_back((node){uu,w});
if(j!=k)
a[uu].push_back((node){vv+n,0}),
a[vv].push_back((node){uu+n,0});
}
}
dij();
int ans=INT_MAX;
for(int i=0;i<=k;i++)
ans=min(ans,dis[i*n+t]);
cout<<ans;
return 0;
}
|
考虑将初始可走与初始不可走的边分层，将有开关的点在两层之间连一条边权为 $0$ 的边，跑最短路。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
struct node{
int v,w;
};
vector<node>a[N];
int dis[N],f[N];
int n,m,k,s=1,t;
struct cmp{
bool operator ()(const node &A,const node &B)
{
return A.w>B.w;
}
};
void dij()
{
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
priority_queue<node,vector<node>,cmp>q;
q.push((node){s,0});
while(!q.empty())
{
node now=q.top();q.pop();
int u=now.v;
if(f[u])continue;
f[u]=1;
for(int i=0;i<a[u].size();i++)
{
int v=a[u][i].v,w=a[u][i].w;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if(!f[v])q.push((node){v,dis[v]});
}
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
if(!w)u+=n,v+=n;
a[u].push_back((node){v,1});
a[v].push_back((node){u,1});
}
for(int i=1;i<=k;i++)
{
int x;
cin>>x;
a[x].push_back((node){x+n,0});
a[x+n].push_back((node){x,0});
}
dij();
int ans=min(dis[n],dis[n*2]);
if(ans>INT_MAX)cout<<"-1";
else cout<<ans;
return 0;
}
|
习题：
P4822 [BJWC2012] 冻结
P2939 [USACO09FEB] Revamping Trails G
P3119 [USACO15JAN] Grass Cownoisseur G
