求神犇帮助

---

这是本蒟蒻的AC代码 然而是靠未知BUG对的

#include <bits/stdc++.h>
using namespace std;


const int N=4000100,M=10000100;
int n,m,k,s,t;
int dis[N],vis[N],head[N],to[M],W[M],NeXt[M],cnt;

typedef pair<int,int> PII;


void add(int u,int v,int w){
	to[cnt]=v;
	W[cnt]=w;
	NeXt[cnt]=head[u];
	head[u]=cnt;
	cnt++;
}


void djikstra(){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	priority_queue<PII, vector<PII>, greater<PII> > heap;
	heap.push({0,s});
	while(!heap.empty()){
		PII pii=heap.top();
		int t=pii.second;
		int diss=pii.first;
		heap.pop();
//		cout << diss << ' ' << t << ' ' << dis[t] << endl;
		if(vis[t]==1 || dis[t]!=diss){
			continue;
		}
		vis[t]=1;
		for(int y=head[t];y!=-1;y=NeXt[y]){
			int v=to[y];
			dis[v]=min(dis[v],diss+W[y]);
			if(dis[v]==diss+W[y]){
				heap.push({dis[v],v});
			}
		}
	}
}


int main(){
	cin >> n >> m >> k >> s >> t;
	memset(head,-1,sizeof(head));
	memset(vis,0,sizeof(vis));
	for(int x=1;x<=m;x++){
		int u,v,w;
		cin >> u >> v >> w;
		add(u,v,w);
		add(v,u,w);
		for(int y=1;y<=k;y++){
			add(u+(y-1)*n,v+y*n,0);
			add(v+(y-1)*n,u+y*n,0);
			add(u+y*n,v+y*n,w);
			add(v+y*n,u+y*n,w);
		}
	}
	
	
	//Question 2
	for(int x=1;x<=k;x++){
		add(t+(x-1)*n,t+x*n,0);
	}
	
	
	
	djikstra();
	int ans=0x3f3f3f3f;
	
	
	
	
	//Question 1
//	for(int x=1;x<=k;x++){
//		ans=min(ans,dis[t+n*x]);
//	}
//	cout << ans;


	cout << dis[t+n*k];
	
	
	
	
	
	return 0;
}

Question 1

for(int x=1;x<=k;x++){
	ans=min(ans,dis[t+n*x]);
}
cout << ans;

注销以上代码,改为直接输出 dis[t+n*k]

使得:

#1,#2,#5,#10 WA --> AC

#11 AC --> WA

为什么跟zhoup讲的完全相反啊QAQ

---

Question 2

for(int x=1;x<=k;x++){
	add(t+(x-1)*n,t+x*n,0);
}

添加以上代码,使得

#11 WA --> AC

添加的是SuperJvRuo大佬的这行预防BUG的代码

但是本蒟蒻没明白什么意思QAQ

请求各位大佬提供详细解析[鞠躬]