CSP-S复习：图论题选讲

今天跟着南外复习的图论，十道题，感觉质量不错，就拿出来总结一下。

一：P3659 [USACO17FEB] Why Did the Cow Cross the Road I G

题意：给你 $n\ast n$ 的方格，可以向上下左右移动，每走 $3$ 步要停留一段时间，从 $(1,1)$ 走到 $(n,n)$ 的最短路。

首先很正常的思路就是先连边建图，然后暴力跑 dijkstra，不过这样会超时（至少我TLE了两个点）。接下来再想，走 $3$ 步才停留一段时间，那就直接按走 $3$ 步所到达的点来连边，然后再跑最短路就可以了。最后统计答案时要注意一下，可能从其他点走到 $(n,n)$ ，具体见代码。

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
const int N=1e5+10;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,T,a[N],dist[N],vis[N],head[N],tot;
int dx[16]={-1,-2,-3,-2,-1,0,1,2,3,2,1,0,-1,0,1,0};//走3步可能到达这些点
int dy[16]={-2,-1,0,1,2,3,2,1,0,-1,-2,-3,0,1,0,-1};
struct node{
int to,nxt,w;
}edge[N*10];
void add(int x,int y,int w){
edge[++tot].to=y;
edge[tot].w=w;
edge[tot].nxt=head[x];
head[x]=tot;
}
int get(int x,int y){
return (x-1)*n+y;
}
void dijkstra(int s){
memset(dist,0x3f,sizeof(dist));
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push(make_pair(0,s)),dist[s]=0;
while(!q.empty()){
int t=q.top().se;q.pop();
if(vis[t]) continue;vis[t]=1;
for(int i=head[t];i;i=edge[i].nxt){
int y=edge[i].to;
if(dist[y]>dist[t]+edge[i].w){
dist[y]=dist[t]+edge[i].w;
q.push(make_pair(dist[y],y));
}
}
}
}
int main(){
n=read(),T=read();
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[get(i,j)]=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=0;k<16;k++){
int nx=i+dx[k],ny=j+dy[k];
if(nx<1||ny<1||nx>n||ny>n) continue;
add(get(i,j),get(nx,ny),a[get(nx,ny)]+T*3);
}
}
}
dijkstra(1);//答案不一定是dist[n][n],我们没有默认一定恰好在（n,n）停留
cout<<min(dist[get(n,n)],min(dist[get(n-1,n)]+T,min(dist[get(n,n-1)]+T,min(dist[get(n-2,n)]+2*T,min(dist[get(n-1,n-1)]+2*T,dist[get(n,n-2)]+2*T)))));
return 0;
}

二：最短路输出路径

题意：一个完全图，多次询问，每次询问 $x->y$ 的最短路径，如果有多条，则输出字典序最小的那一条路径。

这个题还是比较水的。数据范围很小，直接跑 floyd 就行。多开一个数组，记录从某点到另一个点的最短路下一步要到哪。注意一下这道题还有点权。

#include<bits/stdc++.h>
using namespace std;
const int N=210;
int n,m,a[N],g[N][N],dist[N][N];
int main(){
cin>>n>>m;
memset(dist,0x3f,sizeof(dist));
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>dist[i][j],g[i][j]=j;
for(int i=1;i<=n;i++) cin>>a[i];
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int dis=dist[i][k]+dist[k][j]+a[k];
if(dist[i][j]>dis){
dist[i][j]=dis;
g[i][j]=g[i][k];
}
else if(dist[i][j]==dis&&g[i][j]>g[i][k]) g[i][j]=g[i][k];
}
}
}
while(m--){
int x,y;cin>>x>>y;int k=x;
printf("From %d to %d :\n",x,y);
printf("Path: %d",x);
while(x!=y){
x=g[x][y];
printf("-->%d",x);
}
printf("\n");
printf("Total cost : ");
cout<<dist[k][y]<<endl;
}
return 0;
}

三：P3556 [POI2013] MOR-Tales of seafaring

题意：给你 $n$ 个点 $m$ 条边的无向图，多次询问，每次询问 从 $x$ 到 $y$ 是否有长度为 $d$ 的路径。

与某年CSP-J的题非常相似。设从 $x$ 到 $y$ 的最短路为 $dis$。发现反复在一条边上走动，最后可以构造出一个路径长度集合 S = { d i s + 2 k ∣ k ∈ N } S=\left \{ dis+2k_{}|_{}k\in N \right \} S={dis+2k​∣​k∈N}。可是由于图中可能存在与 $dis$ 奇偶性相反，也可以满足条件。这就启示我们分奇偶性来跑最短路，这道题就做完了。

由于询问很多，$n$ 并不是很大，所以还可以把询问离线下来，防止多次重复跑一个点的单源最短路。

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
const int N=5005;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,m,q,head[N],tot,vis[N],dist[N][2],ans[N*N];
struct Node{
int t,d,id;
};
vector<Node> query[N];
struct node{
int to,nxt,w;
}edge[N*2];
void add(int x,int y,int w){
edge[++tot].to=y;
edge[tot].w=w;
edge[tot].nxt=head[x];
head[x]=tot;
}
void spfa(int s){
memset(dist,0x3f,sizeof(dist));
queue<int> q;
for(int i=head[s];i;i=edge[i].nxt){
int y=edge[i].to;
dist[y][1]=1,q.push(y),vis[y]=1;
}
while(!q.empty()){
int t=q.front();q.pop();vis[t]=0;
for(int i=head[t];i;i=edge[i].nxt){
int y=edge[i].to;
if(dist[y][1]>dist[t][0]+1){
dist[y][1]=dist[t][0]+1;
if(!vis[y]) vis[y]=1,q.push(y);
}
if(dist[y][0]>dist[t][1]+1){
dist[y][0]=dist[t][1]+1;
if(!vis[y]) vis[y]=1,q.push(y);
}
}
}
}
int main(){
n=read(),m=read(),q=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
add(x,y,1),add(y,x,1);
}
for(int i=1;i<=q;i++){
int s=read(),t=read(),d=read();
query[s].push_back(Node{t,d,i});
}
for(int i=1;i<=n;i++){
if(query[i].empty()) continue;
spfa(i);
for(Node j:query[i]){
int t=j.t,d=j.d,id=j.id;
if(d%2){
if(dist[t][1]<=d) ans[id]=1;
}
else{
if(dist[t][0]<=d) ans[id]=1;
}
}
}
for(int i=1;i<=q;i++){
if(ans[i]) puts("TAK");
else puts("NIE");
}
return 0;
}

（tips：实测 spfa 比 dijkstra 快了许多，也可能是我实现方式有问题。）

四：P2323 [HNOI2006] 公路修建问题

题意很清楚，就不再赘述了。

建 $n-1$ 条公路，实际上就是在原图中求一个生成树，同时希望至少选 $k$ 条一级边，还要最大边权最小。想到了什么？当然是二分了！

我们二分一个 $mid$，然后对于一级边边权小于等于 $mid$ 的，我们就选上，最后希望选出来的一级边大于等于 $k$，同时最后还要满足能形成一棵生成树。满足这两个条件后，这个 $mid$ 就是可行的。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,m,k,head[N],tot,fa[N],mx;
struct node{
int from,to,nxt,w1,w2;
}edge[N];
void add(int x,int y,int w1,int w2){
edge[++tot].to=y,edge[tot].from=x;
edge[tot].w1=w1,edge[tot].w2=w2;
edge[tot].nxt=head[x];
head[x]=tot;
}
int find(int x){
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
bool check(int mid){
for(int i=1;i<=n;i++) fa[i]=i;
int cnt=0,res=0;
for(int i=1;i<=m;i++){
int x=find(edge[i].from),y=find(edge[i].to);
if(x==y) continue;
if(edge[i].w1<=mid) fa[x]=y,cnt++,res++;
}
for(int i=1;i<=m;i++){
int x=find(edge[i].from),y=find(edge[i].to);
if(x==y) continue;
if(edge[i].w2<=mid) fa[x]=y,res++;
}
return cnt>=k&&res==n-1;
}
int main(){
n=read(),k=read(),m=read();
for(int i=1;i<m;i++){
int x=read(),y=read(),w1=read(),w2=read();
add(x,y,w1,w2);mx=max(mx,w1);
}
int l=0,r=mx,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans<<endl;
return 0;
}

五：P3125 [USACO15OPEN] Bessie’s Birthday Buffet S

这道题乍一看非常复杂，既要求最值，又要满足吃的草的质量是递增的，同时还有能量消耗的限制。这时要先冷静，然后再去仔细分析一下。

可以发现，从一个点移到另一个点，肯定是走的最短路，因为我们对路径移动没有限制，这样题就简化许多了。接下来对于最值问题，可以想一想 dp。由于吃的草的质量是递增的，可以先按草的质量排序，设 $f_i$ 表示吃完点 $i$ 的草后，能得到的最优答案，然后发现状态转移方程非常简单。

即： f i = m a x { f j − d i s i , j } + a i f_i=max\left \{ f_j-dis_{i,j} \right \}+a_i fi​=max{fj​−disi,j​}+ai​。不过转移还是有些细节，具体见代码。

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
const int N=1010;
int n,E,head[N],tot,dis[N][N],vis[N],f[N];
struct node{
int to,nxt,w;
}edge[N*20];
struct point{
int w,id;
}a[N];
bool cmp(point a,point b){return a.w<b.w;}
void add(int x,int y,int w){
edge[++tot].to=y;
edge[tot].w=w;
edge[tot].nxt=head[x];
head[x]=tot;
}
void dijkstra(int s){
memset(dis[s],0x3f,sizeof(dis[s])),memset(vis,0,sizeof(vis));
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push(make_pair(0,s)),dis[s][s]=0;
while(!q.empty()){
int t=q.top().se;q.pop();
if(vis[t]) continue;vis[t]=1;
for(int i=head[t];i;i=edge[i].nxt){
int y=edge[i].to;
if(dis[s][y]>dis[s][t]+edge[i].w){
dis[s][y]=dis[s][t]+edge[i].w;
q.push(make_pair(dis[s][y],y));
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>E;
for(int i=1;i<=n;i++){
cin>>a[i].w;int sz;cin>>sz;
a[i].id=i;
for(int j=1;j<=sz;j++){
int x;cin>>x;
add(i,x,E),add(x,i,E);
}
}
for(int i=1;i<=n;i++) dijkstra(i);//题目范围可以暴力求出两点间最短路
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){//j可以为0，意思是i点之前不吃任何草
if(j==0) f[i]=max(f[i],a[i].w);
else f[i]=max(f[i],f[j]-dis[a[j].id][a[i].id]+a[i].w);//注意i，j和id的区别
}
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,f[i]);
cout<<ans<<endl;
return 0;
}

六：P1073 [NOIP2009 提高组] 最优贸易

无重边无自环的有向图，可能有环，求 $1$ 到 $n$ 路径上的一些值，对此我一般优先考虑 tarjan+dp 的做法，虽然题解中有更简单的，但比较套路的做法好想也好写。

对于此题，先缩点，求出每个新点点权的最大值最小值，然后即两个数组，一个是从起点到当前点路径上的最小值，一个是从起点到当前点的最优答案。拓扑排序 dp就行。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,m,a[N],head[N],tot,he[N],tot2,f[N],g[N],fmx[N],fmn[N],q[N],hh=1,tt=0,ans;
int dfn[N],low[N],tim,stk[N],top,scc[N],cnt,deg[N],vis[N],canto[N];
struct node{
int to,nxt;
}edge[N],e[N];
void add(int x,int y){
edge[++tot].to=y;
edge[tot].nxt=head[x];
head[x]=tot;
}
void ADD(int x,int y){
deg[y]++;
e[++tot2].to=y;
e[tot2].nxt=he[x];
he[x]=tot2;
}
void tarjan(int x){
dfn[x]=low[x]=++tim,vis[x]=1,stk[++top]=x;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(vis[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
int y;cnt++;do{
y=stk[top--],vis[y]=0,scc[y]=cnt;
f[cnt]=max(f[cnt],a[y]),g[cnt]=min(g[cnt],a[y]);
}while(x!=y);
}
}
void toposort(int s){
q[++tt]=scc[s];
fmx[scc[s]]=f[scc[s]]-g[scc[s]];
while(hh<=tt){
int t=q[hh++];
for(int i=he[t];i;i=e[i].nxt){
int y=e[i].to;
g[y]=min(g[y],g[t]);
fmx[y]=max(max(fmx[y],f[y]-g[y]),fmx[t]);
if(!--deg[y]) q[++tt]=y;
}
}
}
int main(){
memset(g,0x3f,sizeof(g));
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++){
int x=read(),y=read(),z=read();
if(z==1) add(x,y);
else add(x,y),add(y,x);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
for(int x=1;x<=n;x++){
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(scc[x]!=scc[y]) ADD(scc[x],scc[y]);
}
}
for(int i=1;i<=cnt;i++) fmx[i]=f[i]-g[i],fmn[i]=g[i];
toposort(1);
cout<<max(fmx[scc[n]],0)<<endl;
return 0;
}

七：P5191 [COCI2009-2010#6] HOLMES

从集合的角度考虑。设初始入度为 $0$ 的点为源点，记 $S_i$ 表示 $i$ 事件发生，则可以推出的所有源点事件可能发生的集合。这个可以用一次拓扑排序求出。

对于 $S_j$ 和 $S_i$，若 $i$ 发生，则 $S_i$ 集合中至少一个点的事件发生，此时只要 $S_i$ 包含在 $S_j$ 集合中，就可以推得 $j$事件也一定发生。可以手玩一下样例理解一下。

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,k,vis[N],head[N],tot,q[N],hh,tt,deg[N];
bitset<N> f[N];queue<int> qq;vector<int> ans;
struct node{
int to,nxt;
}edge[N*N];
void add(int x,int y){
edge[++tot].to=y;
edge[tot].nxt=head[x];
head[x]=tot;
}
void toposort(){
hh=1,tt=0;
for(int i=1;i<=n;i++) if(!deg[i]) q[++tt]=i,f[i][i]=1;
while(hh<=tt){
int t=q[hh++];
for(int i=head[t];i;i=edge[i].nxt){
int y=edge[i].to;
f[y]|=f[t];
if(!--deg[y]) q[++tt]=y;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>k;
for(int i=1;i<=m;i++){int x,y;cin>>x>>y;add(x,y),deg[y]++;}
for(int i=1;i<=k;i++){int x;cin>>x;vis[x]=1,qq.push(x);}
toposort();
while(!qq.empty()){
int t=qq.front();qq.pop(),ans.push_back(t);
for(int i=1;i<=n;i++){
if(vis[i]) continue;
if((f[i]&f[t])==f[t]) vis[i]=1,qq.push(i);
}
vis[t]=-1;
}
sort(ans.begin(),ans.end());
for(int j:ans) cout<<j<<" ";cout<<endl;
return 0;
}

八：P3436 [POI2006] PRO-Professor Szu

也是比较套路的一个题。

给定起点，求所有点到起点的路径数量的最大值及方案。对此考虑建反向边，然后从起点开始拓扑排序 dp。再考虑什么时候路径数量一定大于 $36500$，自然是在环上的点。对此可以 tarjan+dp，但别忘了拓扑排序本身就可以判环。这样这道题就做完了，并且码量也比 tarjan求环少了很多。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,m,f[N],vis[N],head[N],tot,deg[N],ans[N];
queue<int> q;
struct node{
int to,nxt;
}edge[N];
void add(int x,int y){
edge[++tot].to=y;
edge[tot].nxt=head[x];
head[x]=tot;
}
void dfs(int x){
vis[x]=1;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(vis[y]) continue;
dfs(y);
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
add(y,x),deg[x]++;
}
dfs(n+1);//这几行是为了避免n+1到不了点对入度产生影响。
for(int i=1;i<=n+1;i++){
if(!vis[i]){
for(int j=head[i];j;j=edge[j].nxt){
int y=edge[j].to;
deg[y]--;
}
}
}
if(!deg[n+1]) q.push(n+1),f[n+1]=1;
while(!q.empty()){
int t=q.front();q.pop();
for(int i=head[t];i;i=edge[i].nxt){
int y=edge[i].to;
f[y]=min(36501,f[t]+f[y]);//和36501取min，方便之后判断
if(!--deg[y]) q.push(y);
}
}
for(int i=1;i<=n;i++) if(deg[i]) f[i]=36501;//在环上
int tot=0,mx=0;
for(int i=1;i<=n+1;i++){
if(f[i]>mx) mx=f[i],tot=0,ans[++tot]=i;
else if(f[i]==mx) ans[++tot]=i;
}
if(mx==36501) puts("zawsze");
else cout<<mx<<endl;
cout<<tot<<endl;
for(int i=1;i<=tot;i++) cout<<ans[i]<<" ";
return 0;
}

九：P3452 [POI2007] BIU-Offices

先对题目进行转化，发现原图上不连边的两点，在补图上是相连的。同时根据题意，这两点必须在一个集合内。而题中要求最大值，所以我们就转化为求补图中的连通块个数。

但是题目的数据范围不允许我们建出补图并 dfs。考虑用链表加队列维护。

先从链表中取出一点加入队列，再遍历队列，对于当前点，把与它相邻的点打上标记。最后遍历链表，把未打标记的点从链表删除，并加入队列，并入答案。打标记的点就代表在原图中相邻，把标记删去，重复上述步骤。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,m,head[N],tot,pre[N],nx[N],vis[N],st[N],sz[N],ans;
queue<int> q;
struct node{
int to,nxt;
}edge[N*20];
void add(int x,int y){
edge[++tot].to=y;
edge[tot].nxt=head[x];
head[x]=tot;
}
void del(int x){
nx[pre[x]]=nx[x],pre[nx[x]]=pre[x];
}
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++){int x=read(),y=read();add(x,y),add(y,x);}
nx[0]=1;
for(int i=1;i<n;i++) pre[i+1]=i,nx[i]=i+1;
for(int i=1;i<=n;i++){
if(vis[i]) continue;
sz[++ans]=1,q.push(i),del(i),vis[i]=1;
while(!q.empty()){
int t=q.front();q.pop();
for(int j=head[t];j;j=edge[j].nxt){
int y=edge[j].to;
if(vis[y]) continue;
st[y]=1;
}
for(int j=nx[0];j;j=nx[j]){
if(!st[j]) q.push(j),del(j),sz[ans]++,vis[j]=1;
else st[j]=0;
}
}
}
sort(sz+1,sz+1+ans);cout<<ans<<endl;
for(int i=1;i<=ans;i++) cout<<sz[i]<<" ";
return 0;
}

十：[AMPPZ2014] Petrol

这里面最有思维难度，也是最有意思的一道题。

首先起点和终点都是加油站，假设此时在一个不是加油站的点 $x$，从 $x$ 移向 $y$，离 $x$ 最近的加油站是 $u$，则我们先到 $u$ 加满油，再移向 $y$，这样操作是不劣的。因为 $x$ 一定从某个加油站转移过来，所以能从某个加油站到 $x$，那么从 $x$ 出发，一定能到 $u$。

所以考虑重新建图，对于原图中的边 $(x,y)$，设 $st{a}_i$ 表示离 $i$ 最近的加油站， $di{s}_i$ 表示 $i$ 到这个加油站的距离，则有 $add(st{a}_x,st{a}_y,di{s}_x+di{s}_y+e_{x,y}.w)$。

对于 $sta$ 和 $dis$ 两个数组，可以采用多源最短路来求出来，将所有加油站都视作源点，最后的 $dis$ 数组就是每个点到最近的一个源点的距离，这也是比较常用的技巧。

最后把所有询问离线下来，对于一个询问的 $b$，就是问把新图上所有边权大于 $b$ 的边删去，再看 $x$ 和 $y$ 是否连通。

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
const int N=2e5+10;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,m,q,s,head[N],tot,he[N],tot2,dist[N],sta[N],fa[N],vis[N],st[N],ans[N];
struct question{
int x,y,b,id;
}query[N];
bool CMP(question a,question b){return a.b<b.b;}
struct node{
int from,to,nxt,w;
}edge[N*2],e[N*2];
bool cmp(node a,node b){return a.w<b.w;}
void add(int x,int y,int w){
edge[++tot].to=y,edge[tot].from=x;
edge[tot].w=w;
edge[tot].nxt=head[x];
head[x]=tot;
}
void ADD(int x,int y,int w){
e[++tot2].to=y,e[tot2].from=x;
e[tot2].w=w;
e[tot2].nxt=he[x];
he[x]=tot2;
}
void dijkstra(){
memset(dist,0x3f,sizeof(dist));
priority_queue<PII,vector<PII>,greater<PII> > q;
for(int i=1;i<=n;i++) if(st[i]) q.push(make_pair(0,i)),dist[i]=0,sta[i]=i;
while(!q.empty()){
int t=q.top().se;q.pop();
if(vis[t]) continue;vis[t]=1;
for(int i=head[t];i;i=edge[i].nxt){
int y=edge[i].to;
if(dist[y]>dist[t]+edge[i].w){
dist[y]=dist[t]+edge[i].w,sta[y]=sta[t];
q.push(make_pair(dist[y],y));
}
}
}
}
int find(int x){
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
int main(){
n=read(),s=read(),m=read();
for(int i=1;i<=s;i++){int x=read();st[x]=1;}
for(int i=1;i<=m;i++){int x=read(),y=read(),w=read();add(x,y,w),add(y,x,w);}
dijkstra();q=read();
for(int i=1;i<=tot;i++){
if(sta[edge[i].from]==sta[edge[i].to]) continue;
ADD(sta[edge[i].from],sta[edge[i].to],dist[edge[i].from]+dist[edge[i].to]+edge[i].w);
}
for(int i=1;i<=q;i++) query[i].x=read(),query[i].y=read(),query[i].b=read(),query[i].id=i;
for(int i=1;i<=n;i++) fa[i]=i;
sort(query+1,query+1+q,CMP),sort(e+1,e+1+tot2,cmp);
for(int i=1,j=1;i<=q;i++){
while(j<=tot2&&e[j].w<=query[i].b){
int x=find(e[j].from),y=find(e[j].to);
if(x!=y) fa[x]=y;j++;
}
if(find(query[i].x)==find(query[i].y)) ans[query[i].id]=1;
}
for(int i=1;i<=q;i++){
if(ans[i]) puts("TAK");
else puts("NIE");
}
return 0;
}

原文地址：https://blog.csdn.net/summ1ts/article/details/142742284

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！