ABC410的D题能不能用最短路？
查看原帖
ABC410的D题能不能用最短路？
1271341
chu_yh楼主2025/6/15 16:50

ABC410的D题能不能用最短路(Dij)？能得话，求条代码,感谢。

#include<bits/stdc++.h>
using namespace std;
int n,m,head[1002],dis[1002],tot;
bool vis[1002];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > q;
struct edge{
	int Next,to,w;
}e[1003];

void adde(int u,int v,int w){
	e[++tot].to=v;
	e[tot].w=w;
	e[tot].Next=head[u];
	head[u]=tot;
}

int main(){
	memset(dis,0x3f3f3f3f,sizeof(dis));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		adde(u,v,w);
	}
	dis[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(!vis[u]){
			vis[u]=1;
			for(int i=head[u];i;i=e[i].Next){
				int v=e[i].to;
				if((dis[u]^e[i].w)<dis[v]){
					dis[v]=(dis[u]^e[i].w);
					q.push(make_pair(dis[v],v));
				}
			}
		}
	}
	if(dis[n]==0x3f3f3f3f) dis[n]=-1;
	printf("%d",dis[n]);
	return 0;
}
Case NameStatusExec TimeMemory
hand_01.txtAC1 ms3632 KiB
hand_02.txtAC1 ms3760 KiB
hand_03.txtAC1 ms3820 KiB
hand_04.txtAC1 ms3788 KiB
hand_05.txtAC1 ms3560 KiB
hand_06.txtAC1 ms3748 KiB
hand_07.txtAC1 ms3632 KiB
hand_08.txtAC1 ms3868 KiB
random_01.txtAC1 ms3632 KiB
random_02.txtAC1 ms3620 KiB
random_03.txtAC1 ms3872 KiB
random_04.txtAC1 ms3724 KiB
random_05.txtAC1 ms3772 KiB
random_06.txtAC1 ms3680 KiB
random_07.txtAC1 ms3656 KiB
random_08.txtAC1 ms3660 KiB
random_09.txtAC1 ms3872 KiB
random_10.txtAC1 ms3660 KiB
random_11.txtAC1 ms3648 KiB
random_12.txtAC1 ms3680 KiB
random_13.txtWA1 ms3680 KiB
random_14.txtWA1 ms3824 KiB
random_15.txtWA1 ms3760 KiB
random_16.txtAC1 ms3568 KiB
random_17.txtAC1 ms3676 KiB
random_18.txtAC1 ms3876 KiB
random_19.txtAC1 ms3648 KiB
random_20.txtAC1 ms3664 KiB
random_21.txtWA1 ms3736 KiB
random_22.txtWA1 ms3732 KiB
sample_01.txtAC1 ms3752 KiB
sample_02.txtAC1 ms3816 KiB
sample_03.txtAC1 ms3632 KiB
2025/6/15 16:50