已AC但是有奇怪的问题
  • 板块P1119 灾后重建
  • 楼主Xeqwq
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/3/10 22:06
  • 上次更新2023/10/28 06:53:29
查看原帖
已AC但是有奇怪的问题
229373
Xeqwq楼主2022/3/10 22:06

初始化的问题。
第一个代码90分 #10第四万多行WA
第二个代码AC
求:为什么

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int n,m;
const int Maxn=202,INF=0x3f3f3f3f;
int d[Maxn][Maxn];
int g[Maxn][Maxn];
int t[Maxn];
void init()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(i==j) d[i][j]=0;
			else if(g[i][j]) d[i][j]=g[i][j];
				 else d[i][j]=INF;
}
void floyd(int k)
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
	int u,v,w,q,x,y,day;
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>t[i];
	while(m--)
	{
		scanf("%d%d%d",&u,&v,&w);
		g[u][v]=g[v][u]=w;
	}
	init();
	cin>>q;
	int now=0;
	while(q--)
	{
		scanf("%d%d%d",&x,&y,&day);
		while(t[now]<=day&&now<n)
		{
			floyd(now);
			now++;
		}
		if(t[x]>day||t[y]>day||d[x][y]==INF) cout<<-1<<endl;
		else cout<<d[x][y]<<endl;
	}
	return 0;
}
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int n,m;
const int Maxn=205;
int d[Maxn][Maxn];
int t[Maxn];
void floyd(int k)
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
	int u,v,w,q,x,y,day;
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>t[i];
	memset(d,0x3f,sizeof(d));
	for(int i=0;i<n;i++) d[i][i]=0;
	while(m--)
	{
		scanf("%d%d%d",&u,&v,&w);
		d[u][v]=d[v][u]=w;
	}
	cin>>q;
	int now=0;
	while(q--)
	{
		scanf("%d%d%d",&x,&y,&day);
		while(t[now]<=day&&now<n)
		{
			floyd(now);
			now++;
		}
		if(t[x]>day||t[y]>day||d[x][y]==0x3f3f3f3f) cout<<-1<<endl;
		else cout<<d[x][y]<<endl;
	}
	return 0;
}
2022/3/10 22:06
加载中...