社区讨论

RE求调

P5651基础最短路练习题参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lzjkrcwh
此快照首次捕获于
2024/08/07 16:15
2 年前
此快照最后确认于
2024/08/07 16:50
2 年前
查看原帖
如果不考虑解法的正确性的话(肯定没办法AC,复杂度太高了)这个代码为什么会RE嘞
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int inf=0x3f3f3f3f;
const int N=1e6+10;
struct edge{int v,s;};
vector<edge>e[N];
int dis[N];
void solve()
{
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
        e[a].push_back({b,c});
        e[b].push_back({a,c});
	}
	auto dijkstra=[&](int x,int y)->int
	{
	   vector<int>dis(N,inf);dis[x]=0;
       vector<int>vis(N,false);
       priority_queue<PII>q;
       q.push({0,x});
       while(q.size())
       {
           auto t=q.top();q.pop();
           int u=t.second;
           if(vis[u])continue;
           vis[u]=true;
           for(auto y:e[u])
           {
           	  int v=y.v,s=y.s;
           	  if(dis[s]>dis[u]^s)
           	  {
           	  	dis[v]=dis[u]^s;
           	  	q.push({-dis[v],v});
           	  }
           }
       }
       return dis[y];
	};
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		cout<<dijkstra(x,y)<<'\n';
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	solve();
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...