又是一个有关于我的玄学问题
  • 板块学术版
  • 楼主shenxinge
  • 当前回复22
  • 已保存回复22
  • 发布时间2020/7/4 16:36
  • 上次更新2023/11/6 23:40:20
查看原帖
又是一个有关于我的玄学问题
235855
shenxinge楼主2020/7/4 16:36

这个代码他最后一秒总是RE,这是为什么?

#include<bits/stdc++.h>
#define maxn 100100
#define int long long
#define this_word 72340172838076673
using namespace std;
struct Edge
{
	int v,w,nxt;
	Edge(){}
	Edge(int _v,int _w,int _nxt){v=_v,w=_w,nxt=_nxt;}
}edge[maxn];
int ecnt,dis[maxn],head[maxn],n,m,q,s,inq[maxn];
int f[maxn];
void init()
{
	for(int i=0;i<=maxn;i++) f[i]=i;
	memset(head,-1,sizeof(head));
	memset(dis,1,sizeof(dis));
	ecnt=0;
}
void addedge(int u,int v,int w)
{
	edge[ecnt]=Edge(v,w,head[u]);
	head[u]=ecnt++;
}
queue<int> que;
void SPFA(int sss)
{
	dis[sss]=0;
	inq[sss]=true;
	que.push(s);
	while(!que.empty())
	{
		int u=que.front();que.pop();
		inq[u]=false;
		f[u]=sss;
		for(int i=head[u];i!=-1;i=edge[i].nxt)
		{
			int v=edge[i].v,w=edge[i].w;
			if(dis[v]>dis[u]+w||dis[v]==this_word)
			{
				dis[v]=dis[u]+w;
				if(!inq[v])
				{
					que.push(v);
					inq[v]=true;
				}
			}
		}
	}
}
signed main()
{
	init();
	cin >> n >> m;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		if(u>v) swap(u,v);
		addedge(u-1,v,w);
		addedge(v,u-1,-w);
	}
	for(int i=1;i<=n;i++)
	{
		if(f[i]==i) SPFA(i);
	}
	cin >> q;
	while(q--)
	{
		int a,b;
		cin >> a >> b;
		if(f[a-1]==f[b]) cout << dis[b]-dis[a-1] << endl;
		else cout << "Too Hard" << endl;
	}
	return 0;
}


样例输入:

3 2
1 3 10
3 3 5
1
1 2

样例输出:

5

2020/7/4 16:36
加载中...