求助!下载的测试点过了交了没分
查看原帖
求助!下载的测试点过了交了没分
800436
zGinkh楼主2024/9/9 22:37

求助,不知为什么测试点都过了只有no的分

#include <bits/stdc++.h>
using namespace std;
const int M=1e7+10;

int n,m,len=1,u,v,w,h[M],d[M],c[520];
string s[120];
struct lzc{
	int v,w,next;
}g[M];

struct cmp{
	bool operator()(const lzc &x1,const lzc &x2){
		return x1.w>x2.w;
	}
};
priority_queue<lzc,vector<lzc>,cmp> q;
 
void add(int u,int v,int w){
	g[len].v=v;
	g[len].w=w;
	g[len].next=h[u];
	h[u]=len++;
	return;
}
void calculate(string s){
	s+=" ";
	memset(c,0,sizeof c);
	int lenc=0,last=0;
	for(int i=0;i<s.size();i++){
		if(s[i]==' '){
			lenc++;
			for(int j=i-1;j>=last;j--){
				c[lenc]+=pow(10,i-1-j)*(int(s[j])-48);
			}
			last=i+1;
		}
	}
	for(int i=1;i<=lenc;i++){
		for(int j=i;j<=lenc;j++){
			add(c[i],c[j],1);
		}
	}
}
void dijkstra(){
	for(int i=1;i<=n;i++) d[i]=0x3f3f3f3f;
	d[1]=0;
	q.push(lzc{1,0});
	while(!q.empty()){
		lzc head=q.top(); q.pop();
		for(int i=h[head.v];~i;i=g[i].next){
			if(d[g[i].v]>d[head.v]+g[i].w){
				d[g[i].v]=d[head.v]+g[i].w;
				q.push(lzc{g[i].v,d[g[i].v]});
			}
		}
	}
}
int main(){
	memset(h,-1,sizeof h);
	cin>>m>>n;
	for(int i=0;i<=m;i++){
		getline(cin,s[i]);
		if(i!=0) calculate(s[i]);
	}
	dijkstra();
	if(d[n]!=0x3f3f3f3f) printf("%d",d[n]-1);
	else printf("NO");
	return 0;
}

2024/9/9 22:37
加载中...